做中英文网站多少钱色盲眼镜

重新再写一遍DP专题，之前看到题完全不知道怎么写，
现在虽然没有以前那么懵逼不过还是要想好一会

233333
终于没看题解辣自己写开心O(∩_∩)O~~，虽然是个简单题= =算一个好的开始吧继续努力~

 

题意：

N*M的矩阵，从最左边的一列走到最右边的一列;
也就是说，起点可以为第一列的任一行，终点可以是最后一列的任一行。

每个格子可以走到与他相邻的右边的上中下三个格子的任一格子，
第一个格子与最后一个格子相接，可以看成环。也就是说，
第一个的上一个格子是最后一个格子，最后一个格子的下一个格子是第一个格子。

求权值最小的路径，每条路径的权值是经过的格子的数值的和。

输出字典序最小的路径 及 最小权值。

 

解题：

用取余可以解决上下相接的问题。
由于要输出字典序最小的一条路径，所以从最后一列往第一列推，
记下他最小的前驱，然后在第一列找到最小值，沿着前驱输出路径。

 

#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
const int INF = 0x3f3f3f3f;
int a[20][maxn];
int d[20][maxn], pre[20][maxn];int main()
{int n, m;while (scanf ("%d%d", &n,&m) != EOF) {for (int i = 0; i < n; i ++) {for (int j = 0; j < m; j ++) {scanf ("%d", &a[i][j]);}}for (int i = 0; i < n; i ++)d[i][m-1] = a[i][m-1];memset(pre,INF,sizeof(pre));for (int j = m-2; j >= 0; j --) {for (int i = 0; i < n; i ++) {d[i][j] = INF;if (d[(((i-1)%n)+n)%n][j+1] + a[i][j] <= d[i][j]) { // 不断更新走到当前点的最小值int ans = d[(((i-1)%n)+n)%n][j+1] + a[i][j];if(ans < d[i][j]) pre[i][j] = (((i-1)%n)+n)%n;  // 如果有更优解是要无条件的更新的else pre[i][j] = min (pre[i][j], ((((i-1)%n)+n)%n)); // 如果一样就更新前驱d[i][j] = ans;}if (d[i][j+1] + a[i][j] <= d[i][j]) {int ans = d[i][j+1] + a[i][j];if(ans < d[i][j]) pre[i][j] = i;else pre[i][j] = min (pre[i][j], i);d[i][j] = ans;}if (d[(i+1)%n][j+1] + a[i][j] <= d[i][j]) {int ans = d[(i+1)%n][j+1] + a[i][j];if(ans < d[i][j]) pre[i][j] = (i+1)%n;else pre[i][j] = min (pre[i][j], (i+1)%n);d[i][j] = ans;}}}int ans = d[0][0],st = 0;for (int i = 1; i < n; i ++) { // 第一列找到最小值if(d[i][0] < ans) {ans = d[i][0]; st = i;}}printf ("%d",st+1);for (int i = 0; i < m-1; i ++) { //输出路径st = pre[st][i];printf (" %d",st+1);}printf ("\n%d\n", ans);}return 0;
}