最小链覆盖——Dilworth定理，与LIS问题

yuanheci 2023年03月20日 370次浏览

DilworthDilworth 定理：一言以蔽之，偏序集能划分成的最少的全序集个数等于最大反链的元素个数。

该定理在序列问题中的应用：

image-1679296349388

https://blog.csdn.net/qq_43408238/article/details/104542949

与DP中的LIS模型问题结合

注意本文中提到的LIS模型不单单指上升子序列，而是包含上升、严格上升、下降，严格下降子序列的统称。

《导弹拦截》
https://www.luogu.com.cn/problem/P1020

朴素DP（n^2）

状态定义： f[i]f[i] 表示以 ii 结尾的最长 LISLIS 模型。

 for(int i = 1; i <= cnt; i++){
        f[i] = 1;
        for(int j = 1; j < i; j++){
            if(h[j] >= h[i]) f[i] = max(f[i], f[j] + 1);
        }
}

一种贪心 + 二分的思路（nlogn）

  用 DilworthDilworth 定理，将第一问转化成用严格上升子序列的最少覆盖数量。

贪心策略：

  将第一问求最长非上升子序列用Dilworth定理转化成求将序列分解成最少的严格上升子序列的数量。然后第一问和第二问都用贪心思想解决即可，用二分优化到O(nlogn)。

  第一问转化成了用严格上升子序列来覆盖整个序列，第二问就是用不上升序列来覆盖整个序列。

  f，q代表的是拦截系统的末尾高度。

  在这里，如果前面的拦截系统能够拦截到当前的炮弹，那么就不用新开。更新f或者g即可，否则需要新开一个拦截系统。

  对于第一问严格上升序列，只有当目前所有拦截系统的末尾高度都大于等于当前炮弹高度a[i]时，才需要新开一个拦截系统来专门拦截当前炮弹，否则，我们可以用二分在先前的拦截系统中找到严格小于当前高度a[i]的最大值（贪心策略）。然后更新这个拦截系统的末尾高度为a[i]。

  由此可见f是非单调递减的。

  对于第二问的非上升序列，只有当目前所有拦截系统的末尾高度都严格小于当前炮弹高度a[i]时，才需要新开一个拦截系统。否则，我们可以用二分在先前的系统中找到大于等于当前高度a[i]的最小值（贪心策略，不会被浪费）。然后更新这个拦截系统的末尾高度为a[i]。

  由此可见q是单调递增的。

  f和q的单调性影响到二分时的check，因此很重要。

  该做法不能记录以每个点为结尾的LIS模型，只能求出整个序列的最大值。

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int f[N], a[N], q[N], n, k, cnt, x;
int ans;

void solve(){		
	while(scanf("%d", &x) != -1) a[++n] = x;
	
	for(int i = 1; i <= n; i++){
        if(i == 1) {
            f[++k] = a[i], q[++cnt] = a[i];
            continue;
        }
		int l = 1, r = k;
		while(l < r){
			int mid = l + r >> 1;
			if(f[mid] < a[i]) r = mid;  //在递减序列f中二分找严格小于a[i]的最大的数 
			else l = mid + 1;
		}
		if(f[l] >= a[i]) f[++k] = a[i];
		else f[l] = a[i];

		l = 1, r = cnt;
		while(l < r){
			int mid = l + r >> 1;  //在递增序列g中二分找大于等于a[i]的最小的数 
			if(q[mid] >= a[i]) r = mid;
			else l = mid + 1;
		}
        if(q[cnt] < a[i]) q[++cnt] = a[i];
        else q[l] = a[i];
	}
	printf("%d\n%d\n", k, cnt);
}

int main(){
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);   
	int T = 1;
//	scanf("%d", &T);
	while(T -- ){
		solve();
	}
	return 0;
}

完美求解LIS (nlogn)

以下两种方法可以用 O(nlogn)O(nlogn) 的复杂度求出以每个位置结尾的LIS模型

1、利用贪心+二分优化直接求LIS模型

求不上升覆盖数，等价于求严格上升子序列的最大长度。

#include <bits/stdc++.h>
using namespace std;

const int N = 100010, M = 50010;
int f1[N], g1[N], f2[N], g2[N];
int a[N], n, len1, len2;
int res1, res2;

void solve(){
	int x;
	while(scanf("%d", &x) != -1) a[++n] = x; 
	for(int i = 1; i <= n; i++){
		//g1[i]表示长度为i的不上升子序列末尾的最大值,所以g数组本身是递减的
		//二分寻找的是大于等于a[i]的最小的那个数 
		int l = 0, r = len1;
		while(l < r){
			int mid = l + r + 1 >> 1;
			if(g1[mid] >= a[i]) l = mid;
			else r = mid - 1; 
		}
		g1[l + 1] = a[i];
		f1[i] = l + 1;
		len1 = max(len1, l + 1);
		
		//g2[i]表示长度为i的严格上升子序列末尾的最小值
		//二分寻找的是严格小于a[i]的最大的位置。 
		l = 0, r = len2;
		while(l < r){
			int mid = l + r + 1 >> 1;
			if(g2[mid] < a[i]) l = mid;
			else r = mid - 1;
		}
		g2[l + 1] = a[i];
		f2[i] = l + 1;
		len2 = max(len2, l + 1);
	}
	for(int i = 1; i <= n; i++){
		res1 = max(res1, f1[i]);
		res2 = max(res2, f2[i]);
	}
	printf("%d\n%d\n", res1, res2);
}

int main(){
	int T = 1;
//	scanf("%d", &T); 
	while(T -- ){
		solve();
	}	
}

2、树状数组维护求LIS模型

注意树状数组维护的是什么：

  tr[i]tr[i] 表示以 ii 位置的值 a[i]a[i] 结尾的最长上升子序列长度（维护的是值域上的）。
  所以如果求的是最长严格上升子序列，那么就是query(a[i] - 1) + 1，非严格上升子序列，就是query(a[i]) + 1。
  如果是不上升子序列，那么就需要反向遍历，for(int i = n; i >= 1; i--)，因为正向的不上升子序列相当于反向的不下降子序列，同理做一遍即可。

一些 TrickTrick 的地方：

  • 由于使用了树状数组维护，因此要注意query的值不能是0，可以通过全体值加1来避免这个情况。
  • 如果值域范围过大，直接用树状数组维护会MLE，需要离散化。
#include <bits/stdc++.h>
using namespace std;

const int N = 100010, M = 50010;
int tr[M], a[N];
int n, m;
int ans1, ans2;

inline int lowbit(int x){
	return x & -x;
}

void add(int x, int c){
	for(int i = x; i <= m; i += lowbit(i)){
		tr[i] = max(tr[i], c);
	}
}

int query(int x){
	int ans = 0;
	for(int i = x; i; i -= lowbit(i)){
		ans = max(ans, tr[i]);
	}
	return ans;
}

void solve(){
	n = 1;
	while(scanf("%d", &a[n]) != -1) {
		a[n]++;
		m = max(m, a[n]);
		n++;
	}
	n--;
	//正向不上升子序列相当于，反向做一遍不下降子序列 
	for(int i = n; i >= 1; i--){
		int t = query(a[i]) + 1;
		ans1 = max(ans1, t);
		add(a[i], t); 
	}
	memset(tr, 0, sizeof tr);
	//Dilworth定理，转化成求最长严格上升子序列
	for(int i = 1; i <= n; i++){
		int t = query(a[i] - 1) + 1;
		ans2 = max(ans2, t);
		add(a[i], t);
	}
	printf("%d\n%d\n", ans1, ans2);
}

int main(){
	int T = 1;
//	scanf("%d", &T); 
	while(T -- ){
		solve();
	}	
}

《纸飞机》
https://ac.nowcoder.com/acm/contest/3782/C

  注意这里的离散化方式，我用手写二分的方式来离散化本题会报段溢出不太清楚为什么。。。

  用树状数组来维护以 ii 位置结尾的 LISLIS 长度。O(nlogn)O(nlogn)

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int tr[N], h[N], b[N], f[N], r[N];  //r[i]表示LIS中第i个位置能否放置的最大值 
int cnt[N];  //cnt[i]表示LIS中第i个位置能够放置的数量（互相替代情况） 
bool st[N];  //st[i]表示h[i]是否在最长的LIS中 
int n, m, mx;


inline int lowbit(int x){
	return x & -x; 
}

void add(int x, int c){
	for(int i = x; i <= m; i += lowbit(i)){
		tr[i] = max(tr[i], c);
	}
}

int query(int x){
	int ans = 0;
	for(int i = x; i; i -= lowbit(i)){
		ans = max(ans, tr[i]);
	}
	return ans;
}

void solve(){		
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &h[i]);
		b[i] = h[i];
	}
	sort(b + 1, b + 1 + n);
	m = unique(b + 1, b + 1 + n) - (b + 1);
	for(int i = 1; i <= n; i++) h[i] = lower_bound(b + 1, b + 1 + m, h[i]) - b; //从1开始 
	
	//求LIS 
	for(int i = 1; i <= n; i++){
		f[i] = query(h[i]) + 1;
		mx = max(mx, f[i]);   //全局最长LIS 
		add(h[i], f[i]);
	}
	
	r[mx + 1] = INF;
	for(int i = n; i >= 1; i--){
		if(h[i] <= r[f[i] + 1]) {  //说明h[i]可以作为最长LIS中第f[i]个位置的元素 
			st[i] = true;
			r[f[i]] = max(r[f[i]], h[i]);
			cnt[f[i]]++;
		}
	}
	
	for(int i = 1; i <= n; i++){
		printf("%d%c", mx - (st[i] && cnt[f[i]] == 1), " \n"[i == n]);
	}
}

int main(){
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);   
	int T = 1;
//	scanf("%d", &T);
	while(T -- ){
		solve();
	}
	return 0;
}
上一篇： 牛客小白月赛69补题——F题