posted on 2022-10-28 14:11:41 | under 题解 | source
problem
给出一个网格图，其中某些格子有财宝，每次从左上角出发，只能向下或右走。问至少走多少次才能将财宝捡完。此对此问题变形，假设每个格子中有好多财宝，而每一次经过一个格子至多只能捡走一块财宝，至少走多少次才能把财宝全部捡完。
\(n,m\leq 10^3,V\leq 10^6\)。
solution
建模：以右下角 \((n,1)\) 为原点，建立平面直角坐标系。将每一个财宝拍成一个点，放在平面上，如图：
3 1 5 2
2 2 1 2
4 0 3 3
我们希望将“走一次”变成这样的一个问题：选出一些点 \(\{(x_i,y_i)\}\)，使得对于任意 \(x_i<x_j\) 都有 \(y_i\geq y_j\)。我们把一个点的宝藏斜放在一个格子里保证了“走过”这个格子只会取走一个。
把它拍到序列上，相当于需要多少个单调不增的子序列覆盖这些点。
Dilworth 定理：
- 对于一个偏序集，其最少反链划分数等于其最大链的大小。
- 对于一个偏序集，其最少链划分数等于其最大反链的大小。
应用到这道题，就是 单调不增的子序列的数量 = 最长单调递增的子序列的长度。
于是直接 dp 就可以了。
code
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int n,m,a[1010][1010];
LL f[1010][1010];
int mian(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
}
for(int j=1;j<=m;j++){
for(int i=n;i>=1;i--){
f[i][j]=max({f[i+1][j-1]+a[i][j],f[i][j-1],f[i+1][j]});
}
}
printf("%lld\n",*max_element(&f[1][1],&f[n][m]));
return 0;
}
int main(){
for(scanf("%*d");~scanf("%d%d",&n,&m);mian());
return 0;
}
证明
考虑导弹拦截，现在有很多个系统拦截了 \([1,i)\) 的导弹。欲将拦截 \(i\) 号导弹，我们一定是选当前最低的一个系统去拦截。如果导弹飞的比系统还高，那就给它开个系统。这样就感性地证明了 Dilworth 定理。
标签：10,P3974,int,题解,TJOI2015,财宝,include,1010 From： https://www.cnblogs.com/caijianhong/p/solution-P3974.html