首页 > 代码库 > hdu 5092 Seam Carving （简单数塔DP，题没读懂，，不过可以分析样例）
hdu 5092 Seam Carving （简单数塔DP，题没读懂，，不过可以分析样例）
题意：
给一个m*n的矩阵，每格上有一个数。
找从第1行到第m行的一条路径，使得这条路径上的数之和最小。
路径必须满足相邻两行所选的两个数的纵坐标相邻（即一个格子必须是另一个格子的周围八个格子中的一个）
输出每一行取的数的列值。 若有多个答案，则路径要求尽量靠右。
思路：
简单数塔DP。题比较不好读，不过可以分析样例。
代码：
int T,m,n;int a[105][105], f[105][105];int path[105];int main(){ cin>>T; rep(t,1,T){ scanf("%d%d",&m,&n); rep(i,1,m) rep(j,1,n) scanf("%d",&a[i][j]); mem(f,inf); rep(j,1,n) f[1][j]=a[1][j]; rep(i,2,m){ rep(j,1,n){ int y; y=j-1; if(y>=1 && f[i-1][y]+a[i][j]<=f[i][j]) f[i][j]=f[i-1][y]+a[i][j]; y=j; if(y>=1 && f[i-1][y]+a[i][j]<=f[i][j]) f[i][j]=f[i-1][y]+a[i][j]; y=j+1; if(y<=n && f[i-1][y]+a[i][j]<=f[i][j]) f[i][j]=f[i-1][y]+a[i][j]; } } int mins=inf, minsp=-1; rep(i,1,n) if(f[m][i]<=mins) mins=f[m][i],minsp=i; path[m]=minsp; rep2(i,m-1,1){ int v=path[i+1]; int temp=inf, tempP; if(v+1<=n && f[i][v+1]<temp) temp=f[i][v+1],tempP=v+1; if(f[i][v]<temp) temp=f[i][v], tempP=v; if(v-1>=1 && f[i][v-1]<temp) temp=f[i][v-1],tempP=v-1; path[i]=tempP; } printf("Case %d\n",t); rep(i,1,m-1) printf("%d ",path[i]); printf("%d\n",path[m]); }}
hdu 5092 Seam Carving （简单数塔DP，题没读懂，，不过可以分析样例）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。