题目
题目大意
给你一堆区间,将这些区间分成特定的几个集合,使得每个集合中的所有区间的并不为空。
求最大的每组区间的交的长度之和。
思考历程
一开始就认为这绝对是(DP)……
试着找一些性质,结果找不出来……
没办法,只能打个简单的状压(DP)……
正解
首先有个很不显然的结论:
对于两个不重合的区间(a)和(b),如果它们互相包含(即(l_aleq l_b<r_bleq r_a)),那么一定满足:
- (a)和(b)同在一个组内。
- (b)在某个组内,而(a)单独为一组。
证明:
假设存在这样的情况:(a)与其它若干个区间为一组,(b)也和其它的区间(或者没有)为一组。
有个很显然的性质,一个区间集合的子集的答案肯定大于等于这个区间的答案。
因为区间交操作只会使得长度越来越小。
所以,如果在这时将(a)移到(b)的那一组,(a)原来的那一组不会更小;并且由于(a)包含(b),区间交是有交换律的,(a)和(b)的交还是(b),所以(b)的那一组的答案不会变。
因此,这种情况是可以被替代的。
证明了这个结论之后就可以搞事情了。
首先,对于区间(a),如果它跟某个被它包含的(b)一组,那么它并不会有什么贡献;
如果它自己为一组,它才会有贡献,但是这会占掉一个集合的位置。
于是就可以分成两种区间:不包含其它任何区间的区间,和包含了至少一个区间的区间。分别记作(B)集合和(A)集合。
对于(B),如果将所有区间以左端点排序,显然它们的右端点也是有序的。
有了这个优美的性质,分组的时候就是连在一块的区间作为一组。因为这一组的贡献是最左边区间的右端点减去最右边的左端点,如果从连在一块的区间中挖出一个,贡献是不变的。而在这个分组中,很显然我们要在保证贡献最大的同时,消耗的(B)集合内的区间尽量多。
设(f_{i,j})为前(i)个区间,分成了(j)组的贡献。转移显然。
统计答案的时候枚举(B)区间分成了几组,对于剩下的还没有分的组,就在(A)集合中贪心地选择最大的几个即可。
代码
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 210
int n,ns,nb,p;
struct Range{
int l,r;
} q[N],qs[N];
int qb[N],sum[N];
bool bz[N];
inline bool cmps(Range a,Range b){return a.l<b.l;}
int f[N][N];
inline void upd(int &a,int b){a<b?a=b:0;}
int main(){
// freopen("in.txt","r",stdin);
freopen("factory.in","r",stdin);
freopen("factory.out","w",stdout);
scanf("%d%d",&n,&p);
for (int i=1;i<=n;++i)
scanf("%d%d",&q[i].l,&q[i].r);
for (int i=1;i<=n;++i){
bool b=1;
for (int j=1;j<=n && b;++j)
if (q[i].l<=q[j].l && q[j].r<=q[i].r && !(q[i].l==q[j].l && q[i].r==q[j].r))
b=0;
bz[i]=b;
}
for (int i=1;i<=n;++i)
if (bz[i])
qs[++ns]=q[i];
else
qb[++nb]=q[i].r-q[i].l;
sort(qs+1,qs+ns+1,cmps);
sort(qb+1,qb+nb+1);
reverse(qb+1,qb+nb+1);
for (int i=1;i<=nb;++i)
sum[i]=sum[i-1]+qb[i];
memset(f,128,sizeof f);
f[0][0]=0;
for (int i=1;i<=ns;++i)
for (int k=i-1;k>=0;--k){
if (qs[k+1].r<=qs[i].l)
break;
for (int j=0;j<p;++j)
upd(f[i][j+1],f[k][j]+qs[k+1].r-qs[i].l);
}
int ans=0;
for (int j=0;j<=p;++j)
ans=max(ans,f[ns][j]+sum[p-j]);
printf("%d
",ans);
return 0;
}
总结
智商还是太低了……
见到区间问题时,要想想各种类似于单调性的问题……
比如包含之类的……