Bzoj3997 [TJOI2015]组合数学

Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 947 Solved: 690

Description

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

Input

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

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

Output

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

Sample Input

1
3 3
0 1 5
5 0 0
1 0 0

Sample Output

HINT

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

Source

图论 Dilworth定理 DP

Dilworth定理：DAG的最小链覆盖=最大点独立集
最小链覆盖指选出最少的链(可以重复)使得每个点都在至少一条链中
最大点独立集指最大的集合使集合中任意两点不可达

——popoQQQ大爷

猜结论大成功。

这题里“两两不可达”的最长链就是从左下角往右上角走的最长链。

DP方程傻傻分不清该取min还是max，在尝试了全部4种方案以后发现两个都是max才能过样例，于是就假装自己推出来了。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<cmath>
 6 using namespace std;
 7 const int mxn=1005;
 8 int read(){
 9     int x=0,f=1;char ch=getchar();
10     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
11     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
12     return x*f;
13 }
14 int n,m;
15 int mp[mxn][mxn];
16 int f[mxn][mxn];
17 void solve(){
18     memset(f,0,sizeof f);
19     for(int i=1;i<=n;i++)
20         for(int j=m;j;j--)
21             f[i][j]=max(f[i-1][j+1]+mp[i][j],max(f[i-1][j],f[i][j+1]));
22     printf("%d
",f[n][1]);
23     return;
24 }
25 int main(){
26     int i,j;
27     int T=read();
28     while(T--){
29         n=read();m=read();
30         for(i=1;i<=n;i++)
31             for(j=1;j<=m;j++)
32                 mp[i][j]=read();
33         solve();
34     }
35     return 0;
36 }