copy：
Dilworth定理：DAG的最小链覆盖=最大点独立集 最小链覆盖指选出最少的链(可以重复)使得每个点都在至少一条链中
最大点独立集指最大的集合使集合中任意两点不可达
此题中独立的定义即是两点满足一个在左下一个在右上（或在同一格）。于是只需要找一条从左下到右上权值和最大的路径。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<‘0‘||c>‘9‘) {if (c==‘-‘) f=-1;c=getchar();} while (c>=‘0‘&&c<=‘9‘) x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 1010 int T,n,m,a[N][N],f[N][N]; int main() { #ifndef ONLINE_JUDGE freopen("bzoj3997.in","r",stdin); freopen("bzoj3997.out","w",stdout); const char LL[]="%I64d\n"; #else const char LL[]="%lld\n"; #endif T=read(); while (T--) { n=read(),m=read(); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) a[i][j]=read(); for (int i=1;i<=m;i++) f[n+1][i]=0; for (int i=n;i>=1;i--) for (int j=1;j<=m;j++) f[i][j]=max(a[i][j]+f[i+1][j-1],max(f[i+1][j],f[i][j-1])); cout<<f[1][m]<<endl; } return 0; }
原文：https://www.cnblogs.com/Gloid/p/9819277.html