[Description]
传送门 >> http://www.lydsy.com/JudgeOnline/problem.php?id=3997
给出一个网格图，其中某些格子有财宝，每次从左上角出发，只能向下或右走。问至少走多少次才能将财宝捡完。此对此问题变形，假设每个格子中有好多财宝，而每一次经过一个格子至多只能捡走一块财宝，至少走多少次才能把财宝全部捡完。
[Hint]
多组数据，N≤1000,M≤1000.每个格子中财宝数不超过106
[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;
}
|
