本文主要是介绍Codeforces 1132 problem C Painting the Fence —— 取n-2个线段的并集最大，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
You have a long fence which consists of n sections. Unfortunately, it is not painted, so you decided to hire q painters to paint it. i-th painter will paint all sections x such that li≤x≤ri.
Unfortunately, you are on a tight budget, so you may hire only q−2 painters. Obviously, only painters you hire will do their work.
You want to maximize the number of painted sections if you choose q−2 painters optimally. A section is considered painted if at least one painter paints it.
Input
The first line contains two integers n and q (3≤n,q≤5000) — the number of sections and the number of painters availible for hire, respectively.
Then q lines follow, each describing one of the painters: i-th line contains two integers li and ri (1≤li≤ri≤n).
Output
Print one integer — maximum number of painted sections if you hire q−2 painters.
Examples
inputCopy
7 5
1 4
4 5
5 6
6 7
3 5
outputCopy
7
inputCopy
4 3
1 1
2 2
3 4
outputCopy
2
inputCopy
4 4
1 1
2 2
2 3
3 4
outputCopy
3
题意：
给你n个线段，让你取其中n-2个，使得他们的并集最大
题解：
真的，不应该看这个标签的。想了好久，交上去以后发现还可以用DP，而且DP代码很短。
我们按左端点为主关键字，右端点为次关键字排序，然后去包含。如果包含的有大于2个，直接输出，如果1个，那么枚举删掉每一个。如果没有覆盖，那么n^2枚举删掉两个的最大值，由于我们是梯度下降的，那么删掉的肯定是只有中间一段了。不会有分开的情况。
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5;
struct node
{int l,r;bool operator< (const node& a)const{if(l==a.l)return r<a.r;return l<a.l;}
}e[N];
int main()
{int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)scanf("%d%d",&e[i].l,&e[i].r);int ans=0;sort(e+1,e+1+m);int sum=0,sta=0,en=0;for(int i=1;i<=m;i++){en=max(en,e[i].r);sta=max(sta,e[i].l);while(sta<=en)sum++,sta++;}int maxn=1e5;int all=0,del=0;for(int i=1;i<=m;i++){if(e[i].l>=e[all].l&&e[i].r<=e[all].r)del++;elsee[++all]=e[i];}if(del>=2)return 0*printf("%d\n",sum);if(del>=1){for(int i=1;i<=all;i++){sta=max(e[i-1].r+1,e[i].l);if(i==all)en=e[i].r;elseen=min(e[i].r,e[i+1].l-1);ans=max(ans,sum-max(0,en-sta+1));}return 0*printf("%d\n",ans);}for(int i=1;i<all;i++){maxn=1e5;sta=max(e[i-1].r+1,e[i].l);en=min(e[i].r,e[i+1].l-1);int cut=max(0,en-sta+1);sta=max(e[i-1].r+1,e[i+1].l);if(i+1==m)en=e[i+1].r;elseen=min(e[i+1].r,e[i+2].l-1);maxn=min(maxn,cut+max(0,en-sta+1));for(int j=i+2;j<=all;j++){sta=max(e[j-1].r+1,e[j].l);if(j==m)en=e[j].r;elseen=min(e[j].r,e[j+1].l-1);maxn=min(maxn,cut+max(0,en-sta+1));}ans=max(ans,sum-maxn);}printf("%d\n",ans);return 0;
}
这篇关于Codeforces 1132 problem C Painting the Fence —— 取n-2个线段的并集最大的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
