http://acm.hdu.edu.cn/showproblem.php?pid=5092
卡读题，实质是每行取一个点，从上到下找一条路径权值和最小，点可以到达的地方是周围八个格子
类似数塔的dp，需要记录路径，当前行由上一行顶上的三个格子转移而来
#include <iostream> #include <cstdio> #include <queue> #include <cstring> #include <algorithm> #include <stack> using namespace std; int n,m; int a[105][105],dp[105][105],pre[105][105]; int dx[]={-1,-1,-1}; int dy[]={0,1,-1}; struct node{ int x,y; }; int main(){ int T; scanf("%d",&T); for(int cas=1;cas<=T;cas++){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ scanf("%d",&a[i][j]); } } for(int i=0;i<105;i++) for(int j=0;j<105;j++) dp[i][j]=0xfffffff; for(int i=1;i<=m;i++) dp[1][i]=a[1][i]; memset(pre,-1,sizeof(pre)); for(int i=2;i<=n;i++){ for(int j=1;j<=m;j++){ if(j-1>=1 && j+1<=m){ //dp[i][j]=min(dp[i][j],a[i][j]+min(dp[i-1][j],min(dp[i-1][j-1],dp[i-1][j+1]))); int t=min(dp[i-1][j],min(dp[i-1][j-1],dp[i-1][j+1])); if(a[i][j]+t<dp[i][j]){ dp[i][j]=a[i][j]+t; if(dp[i-1][j+1]<=dp[i-1][j-1] && dp[i-1][j+1]<=dp[i-1][j]) pre[i][j]=1; else if(dp[i-1][j]<=dp[i-1][j-1] && dp[i-1][j]<=dp[i-1][j+1]) pre[i][j]=0; else pre[i][j]=2; } } else if(j-1>=1){ //dp[i][j]=min(dp[i][j],a[i][j]+min(dp[i-1][j],dp[i-1][j-1])); int t=min(dp[i-1][j],dp[i-1][j-1]); if(a[i][j]+t<dp[i][j]){ dp[i][j]=a[i][j]+t; if(dp[i-1][j]<=dp[i-1][j-1]) pre[i][j]=0; else pre[i][j]=2; } } else if(j+1<=m){ //dp[i][j]=min(dp[i][j],a[i][j]+min(dp[i-1][j],dp[i-1][j+1])); int t=min(dp[i-1][j],dp[i-1][j+1]); if(a[i][j]+t<dp[i][j]){ dp[i][j]=a[i][j]+t; if(dp[i-1][j+1]<=dp[i-1][j]) pre[i][j]=1; else pre[i][j]=0; } } } } int ans=0xfffffff; int res; for(int i=1;i<=m;i++){ //ans=min(ans,dp[n][i]); if(ans>=dp[n][i]){ ans=dp[n][i]; res=i; } } printf("Case %d\n",cas); stack <node> s; node st; st.x=n;st.y=res; s.push(st); while(1){ if(st.x==1)break; int xx=st.x+dx[pre[st.x][st.y]]; int yy=st.y+dy[pre[st.x][st.y]]; st.x=xx;st.y=yy; s.push(st); } for(int i=1;i<=n;i++){ if(i==1)printf("%d",s.top().y); else printf(" %d",s.top().y); s.pop(); } putchar('\n'); } return 0; }