学步园

建矩阵的时候，不建议走传统的 [行，列] 的方式。为了递推的方便，最好 [列，行] 这样建。我是按照传统的方法做的，中途遇到好几次行、列混淆，dp的大小也声明反了（幸好得的是RE，如果是WA可能又要浪费很多时间）。

关于打印路径：我自己按照UVa #1599 Ideal Path(例题6-20)的方法做（Rujia强烈推荐那道题的原因），虽然有一点麻烦，但是AC了。按照书中这道题给的方法做（用一个next数组）却得了WA。以后再查。

有阶段的动态规划用递推非常直观。其实之前的UVa #1347 Tour (例题9-4)就有一点“阶段”的味道。

Run Time: 0.109s

#define UVa  "LT9-4.116.cpp"		//Unidirectional TSP
char fileIn[30] = UVa, fileOut[30] = UVa;

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>

using namespace std;

//Global Variables. Reset upon Each Case!
const int maxm = 10 + 5, maxn = 100 + 5;
int matrix[maxm][maxn];
int dp[maxn + 1][maxm + 1];
/////

int main() {
    int m, n;       //m: row dimension. n: col dimension.
    while(scanf("%d%d", &m, &n) != EOF) {
        for(int i = 0; i < m; i ++) for(int j = 0; j < n; j ++) scanf("%d", &matrix[i][j]);     //matrix index starts from 1.

        for(int i = 0; i < m; i ++) dp[n-1][i] = matrix[i][n-1];
        for(int i = n-2; i >= 0; i --) {
            for(int j = 0; j < m; j ++) {
                int d1 = (j-1+m)%m;
                int d2 = (j+1)%m;
                dp[i][j] = dp[i+1][j];
                dp[i][j] = min(dp[i][j], dp[i+1][d1]);
                dp[i][j] = min(dp[i][j], dp[i+1][d2]);
                dp[i][j] += matrix[j][i];
            }
        }
        int ans = dp[0][0], ansm = 0;
        for(int i = 0; i < m; i ++) {
            if(dp[0][i] < ans) {
                ans = dp[0][i];
                ansm = i;
            }
        }
        int prevm = ansm;
        vector<int> v;
        v.push_back(ansm);
        for(int i = 0; i < n-1; i ++) {
            int d[3];
            d[0] = prevm;
            d[1] = (prevm-1+m)%m;
            d[2] = (prevm+1)%m;
            int prevans = dp[i][prevm];
            int curm = -1;
            for(int j = 0; j < 3; j ++) {
                if(dp[i+1][d[j]] == prevans - matrix[prevm][i] && (curm == -1 || d[j] <= curm)) {
                    curm = d[j];
                }
            }
            prevm = curm;
            v.push_back(curm);
        }
        for(int i = 0; i < v.size(); i ++) printf("%d%c", v[i]+1, (i!=v.size()-1)?' ':'\n');
        printf("%d\n", ans);

    }

    return 0;
}