UVa 1366 - Martian Mining

链接

传送门

题意

给出两个$n \times m$的矩阵,分别代表两种矿石在每个点的数目,第一种矿石只能从右向左运输,第二种只能从左向右运输,运输管道不能交叉,输出两种矿石运输总量的最大值。

思路

定义状态$dp[i][j][k]$为在从$(1, 1)$到$(i, j)$的矩形运输量的最大值,其中$k$为0时代表在$(i, j)$处向左运输,为1代表向右运输。以$k$为0为例,当$(i, j)$要向左运输时,则从$(i, 1)$到$(i, j - 1)$也要向左运输,则最大值只与$(i - 1, j)$处的最大值有关。从而得到转移方程$dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1]) + a[i][j]$,其中$a[i][j]$代表第一种矿石第i行的前j列的和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <cstring>
#include <algorithm>
#define max(a, b) ((a) < (b) ? (b) : (a))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
typedef long long LL;
const int maxn = 510;
int a[maxn][maxn], b[maxn][maxn];
LL dp[maxn][maxn][2];
int main() {
int n, m;
while (~scanf("%d%d", &n, &m) && (n || m)) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf("%d", &a[i][j]);
a[i][j] += a[i][j - 1];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf("%d", &b[i][j]);
b[i][j] += b[i - 1][j];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1]) + a[i][j];
dp[i][j][1] = max(dp[i][j - 1][0], dp[i][j - 1][1]) + b[i][j];
}
}
printf("%lld\n", max(dp[n][m][0], dp[n][m][1]));
}
return 0;
}