Dilworth定理

学习的是https://blog.csdn.net/qq_34564984/article/details/52993626这篇博客的。

简单来说就两个定理，在严格偏序关系（DAG）中：

①最长反链=最小链覆盖（即可相交的最小路径覆盖）

②最长链=最小反链覆盖

证明就略去了。

洛谷P3974 [TJOI2015]组合数学

题意：在n*m的网格图上，一条路从左上走到右下可以有多条路，一条路的代价是路上的格子最大值。问每个点都至少被经过一次的走的代价最小。

解法：仔细思考可以把题目抽象成：每条链就是从左上走到右下，链的代价是路上最大值，那么答案就是求从左上到右下的最小链覆盖。

根据Dilworth定理，最小链覆盖=最长反链。那么此题的最长反链就是从左下走到右上的路！！并且相邻两点不能同行同列！！那么我们怎么求这个最长反链呢？

直接从左下到右上做一次DP即可，dp[i][j]代表从左下到右上的最长链，那么dp[i][j]=max(dp[i+1][j-1]+a[i][j],max(dp[i+1][j],dp[i][j-1])) ; (注意这里只有从左下来才能加上a[i][j]的值，从左边和下边来不能加)。

DP完了之后dp[1][m]就是答案。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e3+10;
 4 typedef long long LL;
 5 int n,m,a[N][N];
 6 LL dp[N][N];
 7 
 8 int main()
 9 {
10     int T; cin>>T;
11     while (T--) {
12         scanf("%d%d",&n,&m);
13         for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&a[i][j]);
14         for (int i=0;i<=n+1;i++) for (int j=0;j<=m+1;j++) dp[i][j]=0;
15         
16         for (int i=n;i;i--)
17             for (int j=1;j<=m;j++)
18                 dp[i][j]=max(dp[i+1][j-1]+a[i][j],max(dp[i+1][j],dp[i][j-1]));
19         printf("%lld
",dp[1][m]);        
20     }
21     return 0;
22 }

View Code

洛谷P4934 礼物

题意：有

$那么我们暴力n^2连边建图DAG，然后拓扑排序求最长链。这样会获得TLE，我们得优化。$

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<vector>
 5 using namespace std;
 6 const int N=1000000+10;
 7 const int M=(1<<20)+100;
 8 const int INF=0x3f3f3f3f;
 9 int n,k;
10 int a[N],v[M],indeg[M],d[M];
11 int cnt=0,head[M],nxt[M*20],to[M*20];
12 queue<int> q;
13 vector<int> ans[M];
14 
15 void add_edge(int x,int y) {
16     nxt[++cnt]=head[x]; to[cnt]=y; head[x]=cnt;
17 }
18 
19 int main()
20 {
21     scanf("%d%d",&n,&k);
22     for (int i=1;i<=n;i++) scanf("%d",&a[i]);
23     for (int i=0;i<=(1<<k)-1;i++) 
24         for (int j=0;j<k;j++)
25             if ( !(i&(1<<j)) ) {
26                 add_edge(i,i|(1<<j));
27                 indeg[i|(1<<j)]++;
28             }
29     for (int i=1;i<=n;i++) v[a[i]]=1;
30     
31     q.push(0); d[0]=v[0];
32     int maxdep=-INF;
33     while (!q.empty()) {
34         int x=q.front(); q.pop();
35         for (int i=head[x];i;i=nxt[i]) {
36             int y=to[i];
37             d[y]=max(d[x]+v[y],d[y]);
38             maxdep=max(maxdep,d[y]);
39             if (--indeg[y]==0) q.push(y);
40         }
41     }
42     
43     printf("1
%d
",maxdep);
44     for (int i=0;i<=(1<<k)-1;i++)
45         if (v[i]) ans[d[i]].push_back(i);
46     for (int i=1;i<=maxdep;i++) {
47         printf("%d ",ans[i].size());
48         for (int j=0;j<ans[i].size();j++) printf("%d ",ans[i][j]);
49         printf("
");
50     }    
51     return 0;
52 }

View Code