http://acm.timus.ru/problem.aspx?space=1&num=1029
DP,对每一层扫描两遍
1 #include <iostream>
2 using namespace std;
3 const int OO=200000000;
4 int n,m;
5 int map[111][511];
6 int dp[111][511];
7 int pre[111][511];
8 int an,alist[50011];
9 int main(){
10 scanf("%d %d",&n,&m);
11 for (int i=1;i<=n;++i)
12 for (int j=1;j<=m;++j) scanf("%d",&map[i][j]);
13 for (int i=1;i<=n;++i){
14 for (int j=1;j<=m;++j){
15 dp[i][j]=dp[i-1][j]+map[i][j];
16 pre[i][j]=0;
17 }
18 for (int j=2;j<=m;++j) if (dp[i][j]>dp[i][j-1]+map[i][j]){
19 dp[i][j]=dp[i][j-1]+map[i][j];
20 pre[i][j]=-1;
21 }
22 for (int j=m-1;j>0;--j) if (dp[i][j]>dp[i][j+1]+map[i][j]){
23 dp[i][j]=dp[i][j+1]+map[i][j];
24 pre[i][j]=1;
25 }
26 }
27
28 int ans=dp[n][1],ap=1;
29 for (int i=2;i<=m;++i) if (dp[n][i]<=ans&&pre[n][i]==0){
30 ans=dp[n][i];
31 ap=i;
32 }
33 int x=ap,nf=n;
34 while (nf>=1){
35 alist[++an]=x;
36 switch (pre[nf][x]){
37 case -1:--x;continue;
38 case 0:--nf;continue;
39 case 1:++x;continue;
40 }
41 }
42 printf("%d",alist[an]);
43 for (int i=an-1;i>0;--i) printf(" %d",alist[i]);
44 }
45
posted on 2008-11-04 14:33
Joseph 阅读(186)
评论(0) 编辑 收藏 引用