[BZOJ3997][TJOI2015]组合数学(Dilworth定理+DP)

题目名字是什么就不能往那方面想。

每个点拆成a[i][j]个，问题变为DAG最小路径覆盖，由Dilworth定理转成最长反链。

使用Dilworth定理的时候要注意那些点之间有边，这里任意一个点和其右下方的所有点都有边。

从右上往左下DP统计答案即可。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 4 using namespace std;
 5 
 6 const int N=1010;
 7 int T,n,m,a[N][N],dp[N][N];
 8 
 9 int main(){
10     freopen("bzoj3997.in","r",stdin);
11     freopen("bzoj3997.out","w",stdout);
12     for (scanf("%d",&T); T--; ){
13         scanf("%d%d",&n,&m);
14         rep(i,1,n) rep(j,1,m) scanf("%d",&a[i][j]);
15         rep(i,1,m+1) dp[0][i]=0;
16         rep(i,0,n) dp[i][m+1]=0;
17         rep(i,1,n) for (int j=m; j; j--) dp[i][j]=max(dp[i-1][j+1]+a[i][j],max(dp[i-1][j],dp[i][j+1]));
18         printf("%d
",dp[n][1]);
19     }
20     return 0;
21 }