- 1 #include <iostream>
- 2 using namespace std;
- 3 int ivec[10001][10001];
- 4 int dp[10001][10001];
- 5 int que[10001];
- 6 int main()
- 7 {
- 8 int m, n;
- 9 int i, j;
- 10 int tail = 1;
- 11 while (cin >> m >> n)
- 12 {
- 13 que[10001] = { 0 };
- 14 for (i = 1; i <= m; i++)
- 15 {
- 16 for (j = 1; j <= n; j++)
- 17 {
- 18 cin >> ivec[i][j];
- 19 }
- 20 }
- 21 que[0] = ivec[m][n];
- 22 dp[1][1] = ivec[1][1];
- 23 for (i = 2; i <= m; i++)
- 24 {
- 25 dp[i][1] = dp[i - 1][1]+ivec[i][1];
- 26 }
- 27 for (j = 2; j <= n; j++)
- 28 {
- 29 dp[1][j] = dp[1][j - 1]+ivec[1][j];
- 30 }
- 31 for (i = 2; i <= m; i++)
- 32 {
- 33 for (j = 2; j <= n; j++)
- 34 {
- 35 dp[i][j] = ((dp[i - 1][j] < dp[i][j - 1]) ? dp[i][j - 1] : dp[i - 1][j]) + ivec[i][j];
- 36 }
- 37 }
- 38 i = m, j = n;
- 39 while(tail <= m + n - 2)
- 40 {
- 41 if (dp[i - 1][j] >= dp[i][j - 1])
- 42 {
- 43 que[tail++] = ivec[i - 1][j];
- 44 i--;
- 45 }
- 46 else
- 47 {
- 48 que[tail++] = ivec[i][j - 1];
- 49 j--;
- 50 }
- 51 }
- 52 for (i = 1; i <= m; i++)
- 53 {
- 54 for (j = 1; j <= n; j++)
- 55 cout << dp[i][j] << " ";
- 56 cout << endl;
- 57 }
- 58 for (i = m + n - 2; i >= 0; i--)
- 59 cout << que[i] << " ";
- 60 cout << endl;
- 61 cout << dp[m][n] << endl;
- 62 }
- 63 return 0;
- 64 }