题目传送门: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 #include #include #include #include #include #include #include #include #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=0; j--) { for(int i=0; idp[i][0]) { ans=dp[i][0]; first=i; } printf("%d", first+1); //输出第一列的行数 for(int i=first, cnt=0; cnt