好题分享1

Problem Description

Tarzan 非常烦数轴因为数轴上的题总是难度非常大。不过他非常喜欢线段，因为有关线
段的题总是不难，讽刺的是在一个数轴上有 n 个线段，Tarzan 希望自己喜欢的东西和讨厌的
东西不在一起，所以他要把这些线段分多次带走，每一次带走一组，最多能带走 k 次。其实
就是要把这些线段分成至多 k 组，每次带走一组，问题远没有那么简单，tarzan 还希望每次
选择的线段组都很有相似性，我们定义一组线段的相似性是组内线段交集的长度，我们现在
想知道最多分成 k 个组带走，Tarzan 最多能得到的相似性之和是多少？

Input format

第一行两个整数 n 和 k。
接下来 n 行每行两个整数 Li, Ri 表示线段的左右端点。

Output format

一行一个整数，表示最多能得到的相似性之和是多少。

Examples

input 1

5 3
5 10
4 11
6 9
10 30
20 40

output 1

43

input 2

5 3 
5 11
16 22
14 20
10 20
6 10

output 2

18

input 3

7 3 
1 9
2 9
2 10
5 15
3 14
14 18
16 20

output 3

21

Constrains and Notes

对于 20% 的数据满足：\(n ≤ 8; k ≤ 5\)
对于 40% 的数据满足：\(k, n ≤ 12\);
对于 70% 的数据满足：\(n ≤ 100\),
对于 100% 的数据满足：\(1 ≤ k ≤ n ≤ 6000, 1 ≤ Li < Ri ≤ 10^6\);

题解

对于 \(\%20\) 的数据，直接枚举每一个线段在哪一个集合里面即可

时间复杂度：\(O(k^n)\)

对于 \(\%40\) 的数据，\(dfs\) 搜索每一条线段在哪一个集合里面，

进行适当剪枝后可以得到最高 \(40\) 分的部分分，

对于 \(\%70\) 的数据，首先，手玩样例一番，收集性质如下：

①空集组(对答案无贡献)最多只有一组。

证明：若有\(k(k >= 2)\)组空集， 则在这些集合中找出前\(k-1\)条线段放入一个集合， 另外的线段放入剩下的一个集合可增加选出来的\(k-1\)条线段长度的答案贡献。

性质①得证。

②若没有空集的话，可以再观察到一个性质：

对于完全包含另一个线段B的线段A， 则B与A在一组可能会使答案更优(但不一定)，不优的情况会在下文另行考虑。

证明：根据题意可得，对于给出的\(n\)条线段，每条线段都会属于一个集合。

设长度为\(x\)的线段被长度为\(y(y > x)\)的线段包含。

因 \(x\)被\(y\)包含，所以\(x\)与\(y\)分到一组，则\(x\)所在集合对答案的贡献最大为\(x\)。

而若\(x\)与不包含\(x\)的线段分到一组时，在小的方面来说答案不优(整体来看可能更优)。

性质②得证。

下面对于性质②的缺陷作考虑：

性质②是将\(x\)与\(y\)放到一个集合，那我们未考虑到的情况就是\(x\)与\(y\)相分离的情况。

我们考虑\(x\)与\(y\)相分离时怎样最优。

显然当\(y\)单独一个集合时对答案的贡献最大。

当然，上面情况成立的条件是仍有空的集合未被使用。

注：当产生包含关系后，\(y\)对集合已无贡献。

所以我们才可以将\(x\)与\(y\)进行分离操作。

否则，算法正确性无法得以保证。

此时，再结合性质①，对答案无贡献的集合最多只有一个。

我们便有了一种做法：

优先考虑不包含的情况，再将\(x\)与\(y\)进行分离操作，更新答案。

因分离线段操作(只考虑包含别的线段的线段)不会对现有答案产生影响。

所以我们可以进行DP预处理操作。

将线段排序，挑选所有出\(r\)递增且\(l\)递增(不包含)的线段。

此时显然能DP。

设\(f[i][j]\)为前\(i\)条线段选了\(j\)个集合相似度之和。

注：这\(j\)个集合不能有空集，因为我们要给每个空集分发线段，更新答案。

否则答案不优。

考虑第\(j\)个集合放入第\(x+1\sim i\)条线段，

则\(f[i][j]=max(f[x][j-1]+r[x+1]-l[i]|r[x+1]>l[i])\)

转化方程得：\(f[i][j]=max(f[x][j-1]+r[x+1]|r[x+1]>l[i])-l[i]\)

对于 \(\%100\) 的数据，在 \(\%70\) 的数据的基础上进行单调队列优化。

考虑我们选择了多少集合，设为\(p\),

考虑用包含其它线段的线段来更新答案。

则此情况对答案的贡献为

\(f[n][p]\)+包含其它线段的前\(k-p\)长线段长度之和。

再枚举\(p\)取最优值即可。

时间复杂度：\(O(n^2)\),在空间上可以使用滚动数组优化。

code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 6e3 + 5;
int read() {
	int x = 0, f = 1; char ch = getchar();
	while(! isdigit(ch)) f = (ch == '-') ? -1 : 1, ch = getchar();
	while(isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
	return x * f;
}
struct edge { int l, r; } t1[N], t2[N];
int n, k, ans, r, len[N], q[N], head, tail, maxl, tot, cnt, f[2][N];
bool cop(const edge &a, const edge &b) { 
	return (a.r == b.r) ? (a.l > b.l) : (a.r < b.r);
}
int main() {
	n = read(); k = read();
	for(int i = 1; i <= n; i ++) 
		t1[i].l = read(), t1[i].r = read(), len[i] = t1[i].r - t1[i].l;
	sort(len + 1, len + n + 1);
	for(int i = n - k + 2; i <= n; i ++) ans += len[i];//共前 k-1 长 (总前缀和); 
	sort(t1 + 1, t1 + n + 1, cop);
	memset(len, 0, sizeof(len));
	for(int i = 1; i <= n; i ++) {//保证r递增 ;
		if(t1[i].l > maxl) {//若l递增 (这些线段不可互相包含);
			t2[++ cnt] = t1[i];//加入t2(用于DP) ;
			maxl = t1[i].l;
		}
		else len[++ tot] = t1[i].r - t1[i].l;//r递增l递减,加入t1(说明这些线段有包含关系);
	}
	sort(len + 1, len + tot + 1, greater<int>());//长度从大到小排序 ;
	for(int i = 2; i <= n; i ++) len[i] += len[i-1];//求包含其它线段的线段的长度前缀和;
	sort(t2 + 1, t2 + cnt + 1, cop);//这些线段不相互包含 ;
	r = 1;//滚动数组优化;
	for(int i = 1; i <= cnt; i ++) {//保证r递增(已经排序) (预处理操作);
		if(t2[1].r <= t2[i].l) f[0][i] = -1e9;//1号线段与i号线段为空集 ;
		else f[0][i] = t2[1].r - t2[i].l;//1号线段与i号线段有交集 ;
	}
	ans = max(ans, f[0][cnt] + len[k-1]);//1个集合 + (k - 1)个集合 ;
	for(int j = 2; j <= min(k, cnt); j ++, r ^= 1) {//枚举选出j个集合,(j < k);
		q[head = tail = 1] = 1; f[r][1] = -1e9;//滚动数组清零 ;
		for(int i = 2; i <= cnt; i ++) {
			while(head <= tail&&t2[q[head]+1].r <= t2[i].l) head ++; //保证第j个集合对答案的贡献为正;
			if(head <= tail) f[r][i] = f[r^1][q[head]]+t2[q[head]+1].r-t2[i].l;
			else f[r][i] = -1e9;
			while(head <= tail&&f[r^1][i] + t2[i+1].r >= t2[q[tail]+1].r + f[r^1][q[tail]]) tail --;//维护f[x][j-1]+r[x+1]的最大值;
			q[++ tail] = i;
		}
		ans = max(ans, f[r][cnt] + len[k - j]);//j个集合 + (k - j) 个集合 
	}
	cout << ans << endl;
	return 0;
}