「BZOJ-3997」[TJOI2015]组合数学

给出一个网格图,其中某些格子有财宝,每次从左上角出发,只能向下或右走。问至少走多少次才能将财宝捡完。此对此问题变形,假设每个格子中有好多财宝,而每一次经过一个格子至多只能捡走一块财宝,至少走多少次才能把财宝全部捡完。

链接

bzoj-3997

输入

第一行为正整数T,代表数据组数。

每组数据第一行为正整数N,M代表网格图有N行M列,接下来N行每行M个非负整数,表示此格子中财宝数量,0代表没有

输出

输出一个整数,表示至少要走多少次。

样例

输入

1
2
3
4
5
1
3 3
0 1 5
5 0 0
1 0 0

输出

1
10

$N<=1000,M<=1000$每个格子中财宝数不超过$10^6$

题解

真是zz,这道题考试的时候写了三个小时,最后爆成5分,糟逼结论题。

Dilworth定理:DAG的最小链覆盖=最大点独立集
最小链覆盖指选出最少的链(可以重复)使得每个点都在至少一条链中
最大点独立集指最大的集合使集合中任意两点不可达
此题中最大点独立集显然是一个集合满足集合中任意两点都是右上-左下的关系,找出从右上走到左下的最长链即为答案,一个简单的DP。

代码

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
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <cstdlib>
using namespace std;
inline void R(int &v) {
static char ch;
v = 0;
bool p = 0;
do {
ch = getchar();
if (ch == '-') {
p = 1;
}
} while (!isdigit(ch));
while (isdigit(ch)) {
v = (v + (v << 2) << 1) + (ch^'0');
ch = getchar();
}
if (p)v = -v;
}
int ma[1005][1005];
int dp[1005][1005];
int main() {
int T;
int n, m;
R(T);
for (int o = 1; o <= T; ++o) {
memset(ma, 0, sizeof(ma));
memset(dp, 0, sizeof(dp));
R(n), R(m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
R(ma[i][j]);
}
}
for (int i = 1; i <= n; i++)
for (int j = m; j; j--)
dp[i][j] = max(dp[i - 1][j + 1] + ma[i][j], max(dp[i - 1][j], dp[i][j + 1]));
cout << dp[n][1] << '\n';
}
return 0;
}
文章目录
  1. 1. 链接
  2. 2. 输入
  3. 3. 输出
  4. 4. 样例
    1. 4.1. 输入
    2. 4.2. 输出
  5. 5. 题解
  6. 6. 代码