BZOJ3997 [TJOI2015]组合数学

题面在这里

​

把每个物品看作一个点，其实就是求DAG的最小链覆盖

根据\(Dilworth\)定理，DAG最小链覆盖=最大点独立集=最长反链

然后这个网格图就可以DP了

\(f_{i,j}\)表示最长反链左下角在\((i,j)\)的最长长度

\(f_{i,j}=Max\{ f_{i-1,j},f_{i,j+1},f_{i-1,j+1}+a_{i,j} \}\)

​

示例程序：

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
inline char nc(){
	static char buf[100000],*l=buf,*r=buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
inline int red(){
	int res=0,f=1;char ch=nc();
	while (ch<'0'||'9'<ch) {if (ch=='-') f=-f;ch=nc();}
	while ('0'<=ch&&ch<='9') res=res*10+ch-48,ch=nc();
	return res*f;
}

const int maxn=1005;
int tst,n,m,a[maxn][maxn];
ll f[maxn][maxn];
int main(){
	tst=red();
	while (tst--){
		n=red(),m=red();
		for (int i=1;i<=n;i++)
		 for (int j=1;j<=m;j++) a[i][j]=red();
		for (int i=1;i<=n;i++)
		 for (int j=m;j>=1;j--)
		  f[i][j]=max(max(f[i-1][j],f[i][j+1]),f[i-1][j+1]+a[i][j]);
		printf("%lld\n",f[n][1]);
	}
	return 0;
}