1 /*
2 题意：抽象一点就是给两个矩阵，重叠的(就是两者选择其一)，两种铺路：从右到左和从下到上，中途不能转弯，
3 到达边界后把沿途路上的权值相加求和使最大
4 DP：这是道递推题，首先我题目看了老半天，看懂后写出前缀和又不知道该如何定义状态好，写不出状态转移方程，太弱了。
5 dp[i][j]表示以(i, j)为右下角时求得的最大值，状态转移方程：dp[i][j] = max (dp[i-1][j] + sum1[i][j], dp[i][j-1] + sum2[i][j]); sum1表示列的前缀，sum2表示行的前缀
6 */
7 /************************************************
8 * Author :Running_Time
9 * Created Time :2015-8-9 10:18:37
10 * File Name :UVA_1366.cpp
11 ************************************************/
12
13 #include <cstdio>
14 #include <algorithm>
15 #include <iostream>
16 #include <sstream>
17 #include <cstring>
18 #include <cmath>
19 #include <string>
20 #include <vector>
21 #include <queue>
22 #include <deque>
23 #include <stack>
24 #include <list>
25 #include <map>
26 #include <set>
27 #include <bitset>
28 #include <cstdlib>
29 #include <ctime>
30 using namespace std;
31
32 #define lson l, mid, rt << 1
33 #define rson mid + 1, r, rt << 1 | 1
34 typedef long long ll;
35 const int MAXN = 5e2 + 10;
36 const int INF = 0x3f3f3f3f;
37 const int MOD = 1e9 + 7;
38 int a[MAXN][MAXN], b[MAXN][MAXN];
39 int sum1[MAXN][MAXN], sum2[MAXN][MAXN];
40 int dp[MAXN][MAXN];
41
42 int main(void) { //UVA 1366 Martian Mining
43 int n, m;
44 while (scanf ("%d%d", &n, &m) == 2) {
45 if (!n && !m) break;
46 memset (sum1, 0, sizeof (sum1));
47 for (int i=1; i<=n; ++i) {
48 for (int j=1; j<=m; ++j) {
49 scanf ("%d", &a[i][j]); sum1[i][j] = sum1[i][j-1] + a[i][j];
50 }
51 }
52 memset (sum2, 0, sizeof (sum2));
53 for (int i=1; i<=n; ++i) {
54 for (int j=1; j<=m; ++j) {
55 scanf ("%d", &b[i][j]); sum2[i][j] = sum2[i-1][j] + b[i][j];
56 }
57 }
58 memset (dp, 0, sizeof (dp));
59 for (int i=1; i<=n; ++i) {
60 for (int j=1; j<=m; ++j) {
61 dp[i][j] = max (dp[i-1][j] + sum1[i][j], dp[i][j-1] + sum2[i][j]);
62 }
63 }
64 printf ("%d
", dp[n][m]);
65 }
66
67 return 0;
68 }
递推DP UVA 1366 Martian Mining
编译人生，运行世界！