题意：
看白书
要点：
一共三种决策：直行，右上，右下。那么就递推，注意题目中可以从第一列的任意一行出发，而且是环形的，最后还得按字典序输出路径，路径输出就直接用数组记录，因为是倒序递推，所以正序直接可以得到路径。
#include#include #include #include using namespace std;const int inf = 0x3f3f3f3f;int n, m;int a[30][300], d[30][300];int nex[30][300];void dp(){ int ans = inf, first = 0; for (int j = n - 1; j >= 0; j--) { for (int i = 0; i < m; i++) { if (j == n - 1) d[i][j] = a[i][j]; else { int row[3] = { i,i - 1,i + 1 }; if (i == 0) row[1] = m - 1; if (i == m - 1) row[2] = 0; sort(row, row + 3);//先排序可以确保优先选择字典序小的行 d[i][j] = inf; for (int k = 0; k<3; k++)//这里求三种决策的最优解 { int v = d[row[k]][j+1] + a[i][j]; if (d[i][j]>v) { d[i][j] = v; nex[i][j] = row[k];//路径记录，因为是逆序的，所以反向就直接是正序 } } } if (j == 0 && ans > d[i][j])//这里求从第一列的哪一行出发的最优解 { ans = d[i][j]; first = i; } } } printf("%d", first + 1); int i = nex[first][0]; for (int j = 1; j < n; j++)//正序输出的就是路径 { printf(" %d", i + 1); i = nex[i][j]; } printf("\n%d\n", ans);}int main(){ while (scanf("%d%d", &m, &n) != EOF)//注意行列输入对应的m和n { for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) scanf("%d", &a[i][j]); dp(); } return 0;}