https://cn.vjudge.net/problem/UVA-116
题意：给出m行n列的整数矩阵，从第一列任何一个位置出发每次往右，右上或右下走一格，最终到达最后一列，要求经过的整数之和最小。
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 5 const int INF = 0x7FFFFFFF; 6 const int maxn = 1000 + 5; 7 8 int m, n; 9 int a[maxn][maxn]; 10 int dp[maxn][maxn]; 11 int next[maxn][maxn]; 12 13 int main() 14 { 15 //freopen("D:\\txt.txt", "r", stdin); 16 while (cin >> m >> n && m && n) 17 { 18 for (int i = 0; i < m;i++) 19 for (int j = 0; j < n; j++) 20 cin >> a[i][j]; 21 int first = 0; 22 int ans = INF; 23 for (int j = n - 1; j >= 0; j--) 24 { 25 for (int i = 0; i < m; i++) 26 { 27 if (j == n - 1) dp[i][j] = a[i][j]; //边界 28 else 29 { 30 dp[i][j] = INF; 31 int row[3] = { i, i + 1, i - 1 }; 32 if (i == 0) row[2] = m - 1; 33 if (i == m - 1) row[1] = 0; 34 sort(row, row + 3); //重新排序，以便找到字典序最小的 35 for (int k = 0; k < 3; k++) 36 { 37 int v = dp[row[k]][j + 1] + a[i][j]; 38 if (v < dp[i][j]) { dp[i][j] = v; ::next[i][j] = row[k];} 39 } 40 } 41 if (j == 0 && dp[i][j] < ans) { 42 ans = dp[i][j]; first = i; 43 } 44 } 45 } 46 cout << first + 1; 47 for (int i = ::next[first][0], j = 1; j < n; i = ::next[i][j], j++) 48 cout << " " << i + 1; 49 cout << endl << ans << endl; 50 } 51 return 0; 52 }