链接
传送门
题意
给出两个\(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;
}
|