POJ2353 Ministry 二维DP+优化

　　状态方程：f[i][j]= Max{ Max{ sum[j]-sum[k-1]+f[i-1][k] | k<=j } , Max{ sum[k]-sum[j-1]+f[i-1][k] | k>j } }。复杂度O(n*m^2)，如果不优化的话会TLE。分离状态转移方程：

1,k<=j 时，f[i-1][k]-sum[k-1];

2,k>j 时，f[i-1][k]+sum[k];

　　即把与j相关的分离出来，那么维护一个前缀最小和后缀最小就可以了,并且记录位置。

 1 //STATUS:C++_AC_172MS_1040KB
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #include<string.h>
 5 #include<math.h>
 6 #include<iostream>
 7 #include<string>
 8 #include<algorithm>
 9 #include<vector>
10 #include<queue>
11 #include<stack>
12 using namespace std;
13 #define LL __int64
14 #define pii pair<int,int>
15 #define Max(a,b) ((a)>(b)?(a):(b))
16 #define Min(a,b) ((a)<(b)?(a):(b))
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define lson l,mid,rt<<1
19 #define rson mid+1,r,rt<<1|1
20 const int N=510,INF=0x3f3f3f3f,MOD=100000000;
21 const double DNF=100000000000;
22 
23 LL f[110][N],prel[N][2],prer[N][2];
24 int path[110][N],list[110][N];
25 int n,m;
26 
27 int printpath(int cur,int w)
28 {
29     if(cur==1){
30         printf("%d\n",w);
31         return w;
32     }
33     int i,la;
34     la=printpath(cur-1,path[cur][w]);
35     if(cur==n){printf("%d\n",w);return 0;}
36     if(la<=w)for(i=la;i<=w;i++)printf("%d\n",i);
37     else for(i=la;i>=w;i--)printf("%d\n",i);
38     return w;
39 }
40 
41 int main()
42 {
43  //   freopen("in.txt","r",stdin);
44     int i,j,w;
45     LL sum[N],t,ans;
46     while(~scanf("%d%d",&n,&m))
47     {
48         mem(f,INF);
49         for(i=1;i<=n;i++){
50             for(j=1;j<=m;j++)
51                 scanf("%d",&list[i][j]);
52         }
53         sum[0]=0;
54         prel[0][0]=prer[m+1][0]=DNF;
55         for(i=1;i<=m;i++)f[1][i]=list[1][i];
56         for(i=2;i<=n;i++){
57             for(j=1;j<=m;j++){
58                 sum[j]=sum[j-1]+list[i][j];
59                 prel[j][0]=prel[j-1][0];
60                 prel[j][1]=prel[j-1][1];
61                 if((t=f[i-1][j]-sum[j-1])<prel[j][0])
62                     prel[j][0]=t,prel[j][1]=j;
63             }
64             for(j=m;j>=1;j--){
65                 prer[j][0]=prer[j+1][0];
66                 prer[j][1]=prer[j+1][1];
67                 if((t=f[i-1][j]+sum[j])<prer[j][0])
68                     prer[j][0]=t,prer[j][1]=j;
69             }
70             for(j=1;j<=m;j++){
71                 if(prel[j][0]+sum[j]<prer[j][0]-sum[j-1]){
72                     f[i][j]=prel[j][0]+sum[j];
73                     path[i][j]=prel[j][1];
74                 }
75                 else {
76                     f[i][j]=prer[j][0]-sum[j-1];
77                     path[i][j]=prer[j][1];
78                 }
79             }
80         }
81 
82         for(i=1,ans=DNF;i<=m;i++)if(f[n][i]<ans)ans=f[n][i],w=i;
83         printpath(n,w);
84     }
85     return 0;
86 }