BZOJ 3997 【动态规划】

TJOI2015 组合数学

[Description]

传送门 >> http://www.lydsy.com/JudgeOnline/problem.php?id=3997
给出一个网格图,其中某些格子有财宝,每次从左上角出发,只能向下或右走。问至少走多少次才能将财宝捡完。此对此问题变形,假设每个格子中有好多财宝,而每一次经过一个格子至多只能捡走一块财宝,至少走多少次才能把财宝全部捡完。

[Hint]

多组数据,$N≤1000,M≤1000$.每个格子中财宝数不超过$10^6$

[Solution]

看完题目知道显然是DP/递推然而并无思路,看完题解恍然大悟,又一次给自己的智商跪了。
题目有没有一点眼熟–就是二维的拦截导弹啊!!!问最小路径覆盖数,根据Dilworth定理,也就等于最长反链,也就是一条从右上到左下每个点都在前一个点左下(不能在正下或正左)的权值和最大的反链。
有人说这个不好理解,我说一种比较形象的理解:
在这条反链中,任意两点间是不能通过一条路径连起来的,所以反链中有多少个点,就有多少条路径(不然可以把其他点也加入路径),而在反链中的这个点有一定是它自己这条路径上权值最大的点(不然可以将这个点替换成权值比它大的),这就导致了,每条路径要走它的权值这么多遍才一定能取完,所以这条反链的权值和就是问题的答案。
然后就可以愉快地AC辣~

[Code]

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn=1000;
int matrix[maxn][maxn];
int f[maxn][maxn];

int main(){
int kase; scanf("%d",&kase);
while(kase--){
int n,m; scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d",&matrix[i][j]);
memset(f,0,sizeof(f));
f[0][m-1]=matrix[0][m-1];
for(int i=1;i<n;i++) f[i][m-1]=max(f[i-1][m-1],matrix[i][m-1]);
for(int i=m-2;i>=0;i--) f[0][i]=max(f[0][i+1],matrix[0][i]);
for(int i=1;i<n;i++)
for(int j=m-2;j>=0;j--)
f[i][j]=max(f[i-1][j+1]+matrix[i][j],max(f[i-1][j],f[i][j+1]));
printf("%d\n",f[n-1][0]);
}
return 0;
}