题目

题目大意

给你一堆区间，将这些区间分成特定的几个集合，使得每个集合中的所有区间的并不为空。

求最大的每组区间的交的长度之和。

思考历程

一开始就认为这绝对是\(DP\)……

试着找一些性质，结果找不出来……

没办法，只能打个简单的状压\(DP\)……

正解

首先有个很不显然的结论：

对于两个不重合的区间\(a\)和\(b\)，如果它们互相包含（即\(l_a\leq l_b<r_b\leq 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\n",ans);

	return 0;

}

总结

智商还是太低了……

见到区间问题时，要想想各种类似于单调性的问题……

比如包含之类的……

巴特西

6367. 【NOIP2019模拟2019.9.25】工厂

题目

题目大意

思考历程

正解

代码

总结

最新文章

热门文章