CF1510H - Hard Optimization

题目大意

给定$n$个区间$L_i,R_i$，满足其两两之间要么包含要么不交，且所有$L_i,R_i$互不相同

求为每个区间选定$L_i\leq l_i<r_i\leq R_i$，$[l_i,r_i]$仅在端点相交

使得$\sum r_i-l_i$，并且输出方案

分析

乍一看，$L_i,R_i$的关系构成森林

哇树形$dp$

哇输出方案！

树形$dp$还可以输出方案！！！！！！！！！

QQ图片20210506190213.gif

考虑从子树合并$dp$信息，令$dp_{u,i,S}$表示

已经确定$u$的子树内的答案，且向祖先接了$i$个区间

$S$表示 左边以及右边 是否有 待定未匹配 的区间端点

按照$L_i$依次合并每个儿子，两个儿子之间可以将未匹配的端点匹配，加入待选集合

待选集合即指向祖先借的个数

每个点在合并结束之后可以匹配同时新建未匹配的左右端点（实际上就是为了给自己定一个方案区间）

关于输出方案

QQ图片20210506185834.jpg

存储每个转移的前驱指针，包括合并以及每个点最后的决策

暴力回溯每个状态，其中待选集合可以用一个栈处理

分类讨论gogogo！！！！

Snipaste_2021-05-06_18-52-05.png

Snipaste_2021-05-06_18-51-49.png

没错三个都是我

QQ图片20210506185755.gif

可能少讨论了一些，但是没有关系！！！！！！！！

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<bits/stdc++.h>
using namespace std;
typedef pair <int,int> Pii;
#define mp make_pair
#define pb push_back
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
int cmax(int &a,int b){ return a<b?a=b,1:0; }

const int N=2010,P=998244353;

int n;
int L[N],R[N];
int dp[N][N][4],sz[N],len[N],fa[N];
vector <int> E[N];

int X[N],Y[N];
int F[N][4],G[N][4];
int p1[N][N][4],p2[N][N][4];
// p1 存储合并子树的前驱
// p2 存储每个点最后决策时的变化
void dfs(int u) {
	sort(E[u].begin(),E[u].end(),[&](int x,int y){ return L[x]<L[y]; });
    // 叶子暴力赋初值
	if(!E[u].size()) {
		sz[u]=0;
		dp[u][0][0]=R[u]-L[u];
		dp[u][0][1]=R[u];
		dp[u][0][2]=-L[u];
		dp[u][0][3]=0;
		return;
	}
	sz[u]=0;
	for(int v:E[u]) dfs(v);
	memset(F,-63,sizeof F);
	for(int v:E[u]) {
		if(v==E[u][0]) {
			rep(i,0,sz[v]) rep(j,0,3) F[i][j]=dp[v][i][j],p1[v][i][j]=i*16+j;
			sz[u]+=sz[v];
			continue;
		}
		rep(i,0,sz[u]) rep(j,0,3) G[i][j]=F[i][j],F[i][j]=-1e9;
		rep(i,sz[u]+1,sz[u]+sz[v]) rep(j,0,3) F[i][j]=-1e9;
		rep(i,0,sz[u]) rep(a,0,3) rep(j,0,sz[v]) rep(b,0,3) if((a>>1)==(b&1)) {
			if(cmax(F[i+j+(b&1)][(a&1)|(b&2)],G[i][a]+dp[v][j][b])) {
				p1[v][i+j+(b&1)][(a&1)|(b&2)]=j*16+a*4+b;
			}
		}
		sz[u]+=sz[v]+1;
	}
	rep(i,0,sz[u]) rep(j,0,3) {
		if(i && cmax(dp[u][i-1][j],F[i][j])) p2[u][i-1][j]=1;
		if(j&1 && cmax(dp[u][i][j-1],F[i][j]-L[u])) p2[u][i][j-1]=2;
		if(j&2 && cmax(dp[u][i][j-2],F[i][j]+R[u])) p2[u][i][j-2]=3;
		if(j&1 && cmax(dp[u][i][j],F[i][j])) p2[u][i][j]=4;
		if(j&2 && cmax(dp[u][i][j],F[i][j])) p2[u][i][j]=5;
	}
}

stack <Pii> stk;
Pii dfs2(int u,int a,int b) {
	if(!E[u].size()) {
		X[u]=L[u],Y[u]=R[u];
		return mp(L[u],R[u]);
	}
	int typ=p2[u][a][b];
	switch(typ) {
		case 0: { break; }
		case 1: { a+=1; break; }
		case 2: { b+=1; break; }
		case 3: { b+=2; break; }
		case 4: { break; }
		case 5: { break; }
	}
	reverse(E[u].begin(),E[u].end());
	int r=0,lst=-1;
	for(int v:E[u]) {
		int t=p1[v][a][b];
		Pii p=dfs2(v,t>>4,t&3);
		if(t&2) {
			if(lst==-1) r=p.second;
			else stk.push(mp(p.second,lst)),lst=-1;
		}
		if(t&1) lst=p.first;
		a-=(t>>4)+(t&1),b=(t>>2)&3;
	}
	switch(typ) {
		case 0:{ break; }
		case 1:{ X[u]=stk.top().first,Y[u]=stk.top().second,stk.pop(); break; }
		case 2:{ X[u]=L[u],Y[u]=lst; break; }
		case 3:{ X[u]=r,Y[u]=R[u]; break; }
		case 4:{ X[u]=L[u],Y[u]=lst,lst=L[u]; break; }
		case 5:{ X[u]=r,Y[u]=R[u],r=R[u]; break; }
	}
	return mp(lst,r);
}

int main(){
	memset(dp,-63,sizeof dp),scanf("%d",&n);
	rep(i,1,n) scanf("%d%d",L+i,R+i),len[i]=R[i]-L[i];
	rep(i,1,n) {
		rep(j,1,n) if(L[j]<L[i] && R[i]<R[j] && (!fa[i] || len[j]<len[fa[i]])) fa[i]=j;
		if(fa[i]) E[fa[i]].pb(i);
	}
	int ans=0;
	rep(i,1,n) if(!fa[i]) {
		dfs(i);
		ans+=dp[i][0][0],dfs2(i,0,0);
	}
	printf("%d\n",ans);
	rep(i,1,n) printf("%d %d\n",X[i],Y[i]);
}