题目传送门:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=52
题意：
给一个m行n列的矩阵，现让你从最左边走到最右边，求经过路径上的权值最小，并输出路径和最小值，如果有多条路径的权值和都是最小值，输出字典序最小的那一条
走的规则：
1.只能从当前列走到下一列
2.假设当前行是第i行，只能走到下一列的第i-1行、第i行、第i+1行
3.第一行的上一行是最后一行，最后一行的下一行是第一行
思路:
设置dp[i][j]是在第i行第i列时到最后一列的最小值，将整个图存在pl[m][n]里面，那么不难发现对任意一个位置有如下三种决策:
1.dp[i][j]=dp[i-1][j+1]+pl[i][j]
2.dp[i][j]=dp[i][j+1]+pl[i][j]
3.dp[i][j]=dp[i+1][j+1]+pl[i][j]
那么怎么记录路径呢？？？
可以用一个pos[m][n]来记录路径，其值是第i行第j列在满足最优情况下的下一个状态的行数。
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <queue> #include <algorithm> #include <vector> #include <stack> #define INF 0x3f3f3f3f #pragma comment(linker, "/STACK:102400000,102400000") using namespace std; int m, n; int pl[15][110]; int pos[15][110]; int dp[15][110]; int main() { while(~scanf("%d%d", &m, &n)) { memset(pl, 0, sizeof(pl)); memset(pos, 0, sizeof(pos)); for(int i=0; i<m; i++) for(int j=0; j<n; j++) scanf("%d", &pl[i][j]); for(int j=n-1; j>=0; j--) { for(int i=0; i<m; i++) { if(j==n-1) { dp[i][j]=pl[i][j]; continue; } int row[3]={i-1, i, i+1}; //用row数组保存三种决策的行 if(i==0) row[0]=m-1; if(i==m-1) row[2]=0; sort(row, row+3); //排序保证在值相同的情况下，字典序最小 dp[i][j]=INF; for(int k=0; k<3; k++) { int val=dp[row[k]][j+1]+pl[i][j]; if(val<dp[i][j]) { dp[i][j]=val; pos[i][j]=row[k]; //保存路径 } } } } int first; int ans=INF; for(int i=0; i<m; i++) //搜寻最小的值，同时从小到大地搜保证了字典序最小 if(ans>dp[i][0]) { ans=dp[i][0]; first=i; } printf("%d", first+1); //输出第一列的行数 for(int i=first, cnt=0; cnt<n-1; cnt++) { printf(" %d", pos[i][cnt]+1); i=pos[i][cnt]; } printf("\n%d\n", ans); } return 0; }
