https://codeforces.com/contest/1132/problem/C

枚举 + 差分前缀和

题意

有一段[1,n]的线段，有q个区间，选择其中q-2个区间，使得覆盖线段上的点最多为多少？

题解

• 一开始用贪心搞，搞到一半发现需要枚举的情况太多
• 只能用暴力搞，即枚举被去掉的两个区间，那么如何判断去掉哪两个区间比较好？
• 维护去掉后剩下的点数即答案

代码

#include<bits/stdc++.h>

using namespace std;

int n,q,i,j,l[5005],r[5005],a[5005],sum[5005][5],L,R,ql,qr,ans,cnt;

int main(){

	cin>>n>>q;

	for(i=1;i<=q;i++){

		cin>>l[i]>>r[i];

		a[l[i]]++;a[r[i]+1]--;

	}

	for(i=1;i<=n;i++){

		a[i]=a[i-1]+a[i];

		if(a[i])cnt++;

		for(j=0;j<3;j++)sum[i][j]=sum[i-1][j];

		if(a[i]==1)sum[i][1]++;

		if(a[i]==2)sum[i][2]++;

	}

	for(i=1;i<=q;i++){

		for(j=i+1;j<=q;j++){

			L=max(l[i],l[j]);R=min(r[i],r[j]);

			if(L>R)

				ans=max(ans,cnt-(sum[r[i]][1]-sum[l[i]-1][1]+sum[r[j]][1]-sum[l[j]-1][1]));

			else{

				ql=min(l[i],l[j]);qr=max(r[i],r[j]);

				ans=max(ans,

						cnt-(sum[L-1][1]-sum[ql-1][1]+

						sum[qr][1]-sum[R][1]+

						sum[R][2]-sum[L-1][2]));

			}

		}

	}

	cout<<ans;

}