NOIP2023模拟2联测23 负责

题目大意

有$n$个区间$[l_i,r_i]$，每个区间有一个权值$w_i$。把这$n$个区间当成$n$个点，如果两个区间之间有交（包括端点），那么就在这两个区间之间连边。于是，这些点就形成了一个区间图。

现在你希望删除一些区间，使得每个连通块的大小不超过$k$。你需要输出删除区间的最小权值和。

$1\le k\le n\le 2500,1\le l_i\le r\le 10^9,1\le w_i\le 10^9$

题解

因为删除区间比较麻烦，所以我们考虑将问题改成在这些区间中选择若干个区间，使得每个连通块的大小不超过$k$，要求选择若干个区间的最大权值和。

先将区间以右端点为第一关键字，左端点为第二关键字从小到大排序。设$f_i$表示当前已经处理了前$i$个区间，$i$之前的连通块都满足连通块大小不超过$k$，且在选择的区间中编号大于$i$的区间和编号小于等于$i$的区间没有交集的情况下的最大权值和。下面考虑转移。

我们可以用$f_i$来更新$f_j$（$j>i$），即要从$i+1$到$j$之间选择一些区间来构成一个连通块（有可能构成多个连通块，但我们都把它看作一个，来保证可以用连通块大小不超过$k$来判断是否合法，如果最优解中$i+1$到$j$之间要选多个连通块，则总会有另一个$i^{\prime }$满足$i^{\prime }+1$和$j$之间只有一个连通块，$f_i$对$f_j$的贡献就会被$f_{i^{\prime }}$对$f_j$的贡献所覆盖）。

因为区间是以右端点为第一关键字排序的，所以区间$i$肯定是$i$所在连通块中右端点最靠右的区间，那么$i+1$到$j$这些区间既然不和$i$在同一个连通块，则$r_i<l_p$（$i+1\le p\le j$）。那么，我们从$i+1$到$n$枚举$j$：

• 如果当前的$j$不满足$r_i<l_j$，则不能选择$j$
• 如果当前的$j$满足$r_i<l_j$，则可以选择，又因为连通块的大小不能超过$k$，所以我们可以用一个堆来维护这些可以选择的区间，尽量选择权值更大的堆

那么，$f_n$即为选择若干个区间的最大权值和。设所有区间的权值为$sum$，则$sum-f_n$即为最终的答案。

时间复杂度为$O(n^2\log n)$。

code

#include
using namespace std;
const int N=2500;
int n,k;
long long sum=0,f[N+5];
priority_queue<int>q;
struct node{
	int l,r,w;
}w[N+5];
bool cmp(node ax,node bx){
	if(ax.r!=bx.r) return ax.r<bx.r;
	return ax.l<bx.l;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&w[i].l,&w[i].r,&w[i].w);
		sum+=w[i].w;
	}
	sort(w+1,w+n+1,cmp);
	for(int i=0;i<=n;i++){
		long long tmp=0;
		for(int j=i+1;j<=n;j++){
			if(w[j].l>w[i].r){
				tmp+=w[j].w;
				q.push(-w[j].w);
				if(q.size()>k){
					tmp+=q.top();q.pop();
				}
			}
			f[j]=max(f[j],f[i]+tmp);
		}
		while(!q.empty()) q.pop();
	}
	printf("%lld",sum-f[n]);
	return 0;
}
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