UVA116

重新再写一遍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 ("
%d
", ans);
   }
    return 0;
}