[HDOJ5092] Seam Carving（DP，记录路径）
题目链接：https://vjudge.net/problem/HDU-5092
很简单的DP，记录路径的方法也很基础。有一个小小的坑点就是希望输出最靠右的最大结果。
那么在更新的时候，尽可能向右走，并且输出结果的时候，从右到左扫描即可。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 110; 5 int f[maxn][maxn]; 6 int path[maxn][maxn]; 7 int a[maxn][maxn]; 8 int n, m; 9 10 int main() { 11 // freopen("in", "r", stdin); 12 int T, _ = 1; 13 scanf("%d", &T); 14 while(T--) { 15 scanf("%d%d",&n,&m); 16 for(int i = 1; i <= n; i++) { 17 for(int j = 1; j <= m; j++) { 18 scanf("%d", &a[i][j]); 19 } 20 } 21 memset(f, 0x7f, sizeof(f)); 22 memset(path, -1, sizeof(path)); 23 for(int i = 1; i <= n; i++) f[1][i] = a[1][i]; 24 for(int i = 2; i <= n; i++) { 25 for(int j = m; j >= 1; j--) { 26 if(f[i][j] > f[i-1][j-1] + a[i][j]) { 27 path[i][j] = 0; 28 f[i][j] = f[i-1][j-1] + a[i][j]; 29 } 30 if(f[i][j] >= f[i-1][j] + a[i][j]) { 31 path[i][j] = 1; 32 f[i][j] = f[i-1][j] + a[i][j]; 33 } 34 if(f[i][j] >= f[i-1][j+1] + a[i][j]) { 35 path[i][j] = 2; 36 f[i][j] = f[i-1][j+1] + a[i][j]; 37 } 38 } 39 } 40 int ret = 0x7f7f7f7f, id = -1; 41 for(int i = m; i >= 1; i--) { 42 if(ret > f[n][i]) { 43 ret = f[n][i]; 44 id = i; 45 } 46 } 47 stack<int> st; 48 st.push(id); 49 int y = id; 50 for(int i = n; i >= 2; i--) { 51 if(path[i][y] == 0) { 52 y--; 53 } 54 else if(path[i][y] == 2) { 55 y++; 56 } 57 st.push(y); 58 } 59 printf("Case %d ", _++); 60 printf("%d", st.top()); st.pop(); 61 while(!st.empty()) { 62 printf(" %d", st.top()); 63 st.pop(); 64 } 65 printf(" "); 66 } 67 return 0; 68 }