DP, 状态转移方程为T[i][j]=max{T[i][j-1],T[i-1][j],T[i][j+1]}+A[i][j];
由于这个DP方程有后效性, 采用迭代动归(经典题目参见"滑雪")
#include<iostream> using namespace std; const int INF=1000000001; int A[101][503]; int T[101][503]; int from[101][500]; int dir[3][2]={{0,1},{0,-1},{-1,0}}; int m,n; void search(int i,int j) { int x=dir[from[i][j]][0]; int y=dir[from[i][j]][1]; if(i+x==0) { printf("%d",j); return; } search(i+x,j+y); printf(" %d",j); return; } int main() { int i,j,k; int min=INF,flag; scanf("%d%d",&m,&n); for(i=1;i<=m;i++) for(j=1;j<=n;j++) scanf("%d",&A[i][j]); T[1][0]=T[1][n+1]=INF; for(i=1;i<=n;i++) { T[1][i]=A[1][i]; from[1][i]=2; } for(i=2;i<=m;i++) { for(j=0;j<=n+1;j++) T[i][j]=INF; flag=1; while(flag) { flag=0; for(j=1;j<=n;j++) { for(k=0;k<3;k++) { if(T[i+dir[k][0]][j+dir[k][1]]+A[i][j]<T[i][j]) { T[i][j]=T[i+dir[k][0]][j+dir[k][1]]+A[i][j]; from[i][j]=k; flag=1; } } } } } for(i=1;i<=n;i++) { if(T[m][i]<min) { min=T[m][i]; flag=i; } } search(m,flag); printf("/n"); return 0; }
