本文共 1600 字，大约阅读时间需要 5 分钟。
1 /* 2 题意：从上到下，找最短路径，并输出路径 3 DP：类似数塔问题，上一行的三个方向更新dp，路径输出是关键 4 */ 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 using namespace std;18 19 const int MAXN = 1e2 + 10;20 const int INF = 0x3f3f3f3f;21 int a[MAXN][MAXN];22 int dp[MAXN][MAXN];23 int pre[MAXN][MAXN];24 25 void print(int x, int y)26 {27 if (x == 1)28 {29 printf ("%d", y); return ;30 }31 print (x - 1, pre[x][y]);32 printf (" %d", y);33 }34 35 int main(void) //HDOJ 5092 Seam Carving36 {37 //freopen ("C.in", "r", stdin);38 39 int n, m, t, cas = 0;40 scanf ("%d", &t);41 while (t--)42 {43 scanf ("%d%d", &n, &m);44 for (int i=1; i<=n; ++i)45 for (int j=1; j<=m; ++j) scanf ("%d", &a[i][j]);46 memset (pre, 0, sizeof (pre));47 48 for (int i=2; i<=n; ++i)49 for (int j=1; j<=m; ++j) dp[i][j] = INF;50 for (int i=1; i<=m; ++i) dp[1][i] = a[1][i];51 52 for (int i=2; i<=n; ++i)53 {54 for (int j=m; j>=1; --j)55 {56 for (int k=1; k>=-1; --k)57 {58 if (j + k < 1 || j + k > m) continue;59 if (dp[i][j] > dp[i-1][j+k] + a[i][j])60 {61 dp[i][j] = dp[i-1][j+k] + a[i][j];62 pre[i][j] = j + k;63 }64 }65 }66 }67 68 int k = m; int mn = dp[n][m];69 for (int i=m-1; i>=1; --i)70 {71 if (mn > dp[n][i]) {mn = dp[n][i]; k = i;}72 }73 74 printf ("Case %d\n", ++cas);75 print (n, k);76 puts ("");77 }78 79 return 0;80 }81 82 /*83 Case 184 2 1 1 285 Case 286 3 2 1 1 2 187 */
转载于:https://www.cnblogs.com/Running-Time/p/4523061.html