JZOJ 6367.工厂

区间题套路:考虑所有区间互不相交的情况,并考虑互相包含的区间之间的关系。
此题类似。

首先考虑所有区间互不相交的情况。
区间按左端点排序(此时右端点一定也有序),这样一组必定是一段区间。
并且只要交集不为空,交集大小即这一组第一个区间右端点减去最后一个区间左端点。

于是得到一个 DP:设 fi,jf_{i,j} 表示前 ii 个区间分 jj 组的最大答案。
转移即枚举该组的区间,得

fi,j=max1ki,tk>si(fk1,j+tksi)f_{i,j} = \max\limits_{1\le k\le i,t_k > s_i}(f_{k-1,j} + t_k - s_i)

然后考虑互相包含的区间之间的关系。
若区间 a,ba,b 满足 bab \subseteq a,则只有以下两种情况:

  1. a,ba,b 与某些区间在同一组。
  2. aa 单独在一组,bb 与某些区间在一组。 证明:若 aa 与某些区间在一组,则将 aa 移动到 bb 所在的组,aa 原来的组交集不会变小,bb 所在的组答案不变。

于是把不包含别的区间的区间拉出来 DP,枚举这一部分在 pp 组中占了多少组,别的组贪心地在另一部分取更大的区间,剩下的分进任意一个所包含的区间所在的组(答案不变)。

代码:

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <functional>
using namespace std;
const int N = 200;
int n,p;
int vis[N + 5];
int tot1,tot2;
int f[N + 5][N + 5],ans = -0x3f3f3f3f;
struct note
{
int l,r;
inline bool operator<(const note &o) const
{
return l < o.l;
}
inline bool operator>(const note &o) const
{
return r - l > o.r - o.l;
}
} w[N + 5],a[N + 5],b[N + 5];
int main()
{
freopen("factory.in","r",stdin),freopen("factory.out","w",stdout);
scanf("%d%d",&n,&p);
for(register int i = 1;i <= n;++i)
scanf("%d%d",&w[i].l,&w[i].r);
for(register int i = 1,flag;i <= n;++i)
{
flag = 1;
for(register int j = 1;j <= n;++j)
if((i ^ j) && !vis[j] && w[i].l <= w[j].l && w[j].r <= w[i].r)
{
flag = 0;
break;
}
flag ? (a[++tot1] = w[i]) : (vis[i] = 1,b[++tot2] = w[i]);
}
sort(a + 1,a + tot1 + 1),sort(b + 1,b + tot2 + 1,greater<note>()),memset(f,-0x3f,sizeof f),f[0][0] = 0;
for(register int i = 1;i <= tot1;++i)
for(register int j = 1;j <= p;++j)
for(register int k = 1;k <= i;++k)
if(a[k].r > a[i].l)
f[i][j] = max(f[i][j],f[k - 1][j - 1] + a[k].r - a[i].l);
for(register int i = p,sum = 0;i && p - i <= tot2;sum += b[p - i + 1].r - b[p - i + 1].l,--i)
i <= tot1 && (ans = max(ans,f[tot1][i] + sum));
printf("%d\n",ans);
}