线段并交问题——抓住包含关系 / 转移贡献用端点加减表示 ： 0922T3

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133175632

http://cplusoj.com/d/senior/p/SS230922C

首先有个贪心，按长度从大往小选，是错的

然后有个dp，按左端点排完后选连续段，也是错的

但把上面两个结合起来，还是错的

然后此时错的有个共性，就是存在区间包含关系

然后我们把区间包含关系去掉，另外统计贡献，那样是对的

只不过超时而已

然后发现dp转移的贡献函数可以直接拿端点值之差来表示

然后就可以前缀和了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 5010
//#define M
//#define mo
struct node {
	int l, r, len; 
}a[N];
int n, m, i, j, k, T, sum;
int ans, l, r, s[N][N], f[N][N], b[N], p[N], g[N][N]; 
int mx; 

void sol1() {
	l=0; r=1e9; 
	sort(a+1, a+n+1, [] (node x, node y) { return x.len>y.len; }); 
	for(i=1; i<m; ++i) sum+=a[i].len; 
	for(i=m; i<=n; ++i) l=max(l, a[i].l), r=min(r, a[i].r); 
	sum+=max(0ll, r-l);
	ans=max(ans, sum); 
}

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
	freopen("se.in", "r", stdin);
	freopen("se.out", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}
	n=read(); m=read(); 
	for(i=1; i<=n; ++i) {
		a[i].l=read(); a[i].r=read(); a[i].len=a[i].r-a[i].l; 
	}
	sol1(); 
	for(i=1; i<=n; ++i)  
		for(j=1; j<=n; ++j)
			if(i!=j) {
				if(a[j].l<=a[i].l && a[j].r>=a[i].r) p[j]=1; 
			}
	for(i=1, j=0; i<=n; ++i) if(p[i]) b[++j]=a[i].len; 
	sort(b+1, b+j+1, [] (int x, int y) { return x>y; }); 
	partial_sum(b+1, b+j+1, b+1); 
	for(i=1, j=0; i<=n; ++i) if(!p[i]) a[++j].l=a[i].l, a[j].r=a[i].r; n=j; 
	sort(a+1, a+n+1, [] (node x, node y) { return x.l<y.l; }); 

	memset(f, 0x80, sizeof(f)); 
	memset(g, 0x80, sizeof(g)); 
	f[0][0]=0; g[0][0]=a[1].r; 

	
	for(j=1; j<=n; ++j) {
		mx=0; 
		for(i=0; i<j; ++i) mx=max(mx, g[i][j-1]); 
		for(i=j; i<=n; ++i) {
			f[i][j]=max(0ll, mx-a[i].l); 
			g[i][j]=f[i][j]+a[i+1].r; 
			
			mx=max(mx, g[i][j-1]); 
		}
	}
		
				
					
			
	for(j=0; j<=m; ++j) ans=max(ans, f[n][j]+b[m-j]); 
	printf("%lld", ans); 
	
	
	return 0;
}