链接
https://ac.nowcoder.com/acm/contest/11253/G
题意
将 $n$ 个区间 $[l_i,r_i)$ 分配到 $k$ 组，使每组交集的和最大，每组都不能为空。
思路
考虑按顺序依次分配区间，每次分配可以分为三种情况：
- 某组为空；
- 某组交集包含于当前区间；
- 某组交集不包含于当前区间。
放入第一种情况，总贡献增加；
放入第二种情况，总贡献不变；
放入第三种情况，总贡献减小。
只可能放入前两种情况的组内，因此可以在一开始将包含小区间的大区间挑出来。
将区间按左端点从小到大，右端点从大到小排序，单调栈处理出所有大区间。
这些大区间放入第二种情况因为交集不变所以不需要考虑，只需要考虑单独放入空的组内。
对于剩下的小区间，将左端点从小到大考虑 DP，记 $dp_{i,j}$ 为前 $j$ 个区间分为 $i$ 组的最大贡献。
在分配时只可能将连续的几个区间放入同个组内，因为这样才能使交集尽可能大。
所以 $dp_{i,j}=\max{dp_{i-1,t-1}+r_t-l_j}=\max{dp_{i-1,t-1}+r_t}-l_j$ $(r_t>l_j)$
可以用单调队列优化，时间复杂度为 $O(nk)$。
当 $i>j$ 时，并不存在分配方案，因此将数组初始化为一个极小值，而 $dp_{0,0}=0$。
如果存在 $k-i$ 个大区间，那么可以更新答案。
将大区间按长度从大到小排序，如果分配时剩下空的组用大区间去填充，每个组依次选较大的一个区间填充，剩下的大区间放入其子集所在组。
代码
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
| #include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const int N=5005;
int dp[N][N],sum[N];
PII a[N];
VPII b;
VI c;
bool cmp(PII a,PII b) {
return a.FI<b.FI||a.FI==b.FI&&a.SE>b.SE;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,k;cin>>n>>k;
for(int i=0;i<n;i++) cin>>a[i].FI>>a[i].SE;
sort(a,a+n);
for(int i=0;i<n;i++) {
while(SZ(b)&&a[i].SE<=b.back().SE) {
c.PB(b.back().SE-b.back().FI);
b.pop_back();
}
b.PB(a[i]);
}
sort(ALL(c),greater<int>());
for(int i=0;i<SZ(c);i++) sum[i+1]=sum[i]+c[i];
memset(dp,0xc0,sizeof dp);
dp[0][0]=0;
int res=0;
for(int i=1;i<=k;i++) {
deque<int> q;
for(int j=0;j<SZ(b);j++) {
while(SZ(q)&&dp[i-1][q.back()]+b[q.back()].SE<=dp[i-1][j]+b[j].SE) q.pop_back();
while(SZ(q)&&b[q[0]].SE<=b[j].FI) q.pop_front();
q.PB(j);
dp[i][j+1]=dp[i-1][q[0]]+b[q[0]].SE-b[j].FI;
}
if(SZ(c)>=k-i) res=max(res,dp[i][SZ(b)]+sum[k-i]);
}
cout<<res<<'\n';
return 0;
}
|