打印路径的 dp 思路 ## 题目描述:
** 给出一个 m*n (m<=10,n<=100) 的矩阵,从第一列的某一位置出发,
每次向右,右上或右下走一格,最终到达最后一列,整个矩阵是环形的,
要求经过的整数和最小,输出最优解及路径所经过的行号 **
思路:
多段图 dp
因为要求路径,所以设 d (i,j) 为以 (i,j) 为起点的最短路径和,
用 nxt (i,j) 表示路径上下一列的行号
则答案为 min {d (k,1)}(1<=k<=n)
状态转移方程见代码
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
| #include <iostream> #include <cstdio> #include <climits> #include <cstring> #include <algorithm> using namespace std; const int Mm(25); const int Mn(105); int nxt[Mm][Mn]; int mp[Mm][Mn],d[Mm][Mn]; int main() { int m,n; while(scanf("%d %d",&m,&n)==2) { memset(mp,0,sizeof mp); for(int i(1);i<=m;++i) for(int j(1);j<=n;++j) scanf("%d",&mp[i][j]); memset(d,0x3f,sizeof d); memset(nxt,0,sizeof nxt); for(int i(1);i<=m;++i) d[i][n] = mp[i][n]; for(int i(n-1);i>=1;--i) { for(int j(1);j<=m;++j) { int nr[3] = {j,j-1,j+1}; if(j==1) nr[1] = m; if(j==m) nr[2] = 1; sort(nr,nr+3); for(int k(0);k<3;++k) { if(d[nr[k]][i+1]+mp[j][i]<d[j][i]) { d[j][i] = d[nr[k]][i+1]+mp[j][i]; nxt[j][i] = nr[k]; } } } } int ans(INT_MAX), p(0); for(int i(1);i<=m;++i) if(d[i][1]<ans) { ans=d[i][1]; p=i; } for(int i(1);i<=n;++i) { if(i!=1) cout << " "; cout << p; p = nxt[p][i]; } cout << endl << ans << endl; } return 0; }
|