[\(TJOI2015\)]组合数学
链接:https://www.luogu.com.cn/problem/P3974
题面:有一个\(n\times m\)的网格，有些格子里有财宝，每次从左上角出发,只能往右或下走且每一次经过一个格子至多只能捡走一块财宝，求最少多少次能将财宝捡完。
题解:铭记这个公式:最小链覆盖=最长反链，这是解这道题的关键。
可以发现，题目要我们求的是要用最少的链覆盖所有的点，所以利用上述公式,我们可以先求出最长反链，最长反链即为从左下角到右上角的最大独立集。
令\(dp_{i,j}\)表示从左下角到\((i,j)\)的最长反链，则有如下转移：
\(dp_{i,j}=max(dp_{i+1,j-1}+a_{i,j},dp_{i+1,j},dp_{i,j-1})\)
对角线\(dp\)即可。
#include<iostream>
using namespace std;
long long dp[5001][5001],a[5001][5001],n,m;
int main()
{
int t;
cin>>t;
while (t--)
{
cin>>n>>m;
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
{
cin>>a[i][j];
dp[i][j]=0;
}
for (int i=1;i<=n+m-1;++i)
for (int j=max(1ll,n-i+1),k;j<=min(n,n+m-i);++j)
{
k=i+j-n;
dp[j][k]=max(dp[j+1][k-1]+a[j][k],max(dp[j+1][k],dp[j][k-1]));
}
cout<<dp[1][m]<<endl;
}
return 0;
}