「BZOJ3997」[TJOI2015]组合数学

Description

组合数学中有一个经典问题是这样的:给出一个网格图,其中某些格子有财宝,每次从左上角出发,只能向下或右走。问至少走多少次才能将财宝捡完。

此题为对此问题变形,假设每个格子中有好多财宝,而每一次经过一个格子至多只能捡走一块财宝,至少走多少次才能把财宝全部捡完?

Input

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

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

Output

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

Sample Input

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

Sample Output

1
10

HINT

N1000,M1000N \leq 1000,M \leq 1000。每个格子中财宝数不超过 10610^6

Solution

链式是的集合,任意两个点uuvv,要么uu能走到vv,要么vv能走到uu
最小链覆盖:用最少的链,经过所有的点至少一次。
Dilworth定理 DAG的最小链覆盖=最大点独立集
最大点独立集 指最大的集合使集合中任意两点不可达
(i,j)(i,j)(i1,j+1)(i-1,j+1)显然是个互不联通的独立集。
fi,jf_{i,j}表示(i,j)(i,j)(1,n)(1,n)这个矩阵里的最大独立集大小。
转移显然。

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 1100, M = N * N * 3;
int n, m;
int a[N][N], f[N][N];
int main() {
int T = read();
while(T--) {
n = read(), m = read();
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
a[i][j] = read();
for(int i = 1; i <= n; ++i) {
for(int j = m; j >= 1; --j)
f[i][j] = max(max(f[i - 1][j], f[i][j + 1]), f[i - 1][j + 1] + a[i][j]);
}
writeln(f[n][1]);
memset(f,0,sizeof f);
}
return 0;
}