Overview
和[email protected]聊天吹水的时候发现自己好久没有做题了2333，加上之前一起被一个题搞自闭了去看他的题解看到了这个题。
题目描述
题目描述
一开始把题目读成了每一步都可以选择往左或者往上，然后？？？
题解
既然传输过程中不能转弯，那么第一种矿就只能往左，第二种矿只能往上。令$f_{i,j}$表示以$(i,j)$为右下角的矩形的答案，对于第一种矿做行的前缀和$a_{i,j}$，对第二种矿做列的前缀和$b_{i,j}$，那么有$f_{i,j}=max{f_{i-1,j}+a_{i,j}, f_{i,j-1}+b_{i,j}}$，答案是$f_{n,m}$.
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
|
#define N 550
using namespace std;
int n, m, a[N][N], b[N][N], f[N][N];
inline void (int& x) {
x = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar());
for (; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
}
int main() {
for (;;) {
read(n), read(m);
if (n == 0 && m == 0) break;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
read(a[i][j]), a[i][j] += a[i][j - 1];
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
read(b[i][j]), b[i][j] += b[i - 1][j];
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
f[i][j] = max(f[i - 1][j] + a[i][j], f[i][j - 1] + b[i][j]);
printf("%dn", f[n][m]);
}
return 0;
}
|
近期评论