把若干区间分成两个集合（可以有的区间不放在任意集合中），使得任意的a∈A，b∈B，a、b区间没有交集
求较小集合最大能是多少
n<=200
区间不交，直接处理只能状压了吧。。。排序什么的都没有用
但是发现，区间一定是一段黑色，一段白色
n<=200
把一段直接分配给某种颜色！
离散化先，
in[l][r]完全在(l,r)中的区间
pre[i][j]，(1,i)，某个集合选择了j个，另一个集合最大选择多少。转移时候枚举最后一段都给一个集合
bac[i][j]，(i,T),.....同理
第一问就是：max(pre[T][i],i)
第二问：
强制必须选择，那么这个区间一定被某个连续段包含。枚举连续段
先设：f[l][r]，强制完全在[l,r]中的区间都给某个集合时，最小的集合最大能是多少
枚举左右各选择几个，用min(x+in[l][r]+y，pre[l][x]+bac[r][y])更新
O(n^4)
发现x不变时，y作为自变量，x+in[l][r]+y是增函数，而pre[l][x]+bac[r][y]是减函数
所以，x变大，y必须变小，整个min才可能更大
决策单调性！
O(n^3logn)
进一步发现，整个min函数是单峰的函数，所以下一个不优的时候直接break
对y维护指针平移。
（一般决策单调性绝对不能这么做）
O(n^3)
Code：
#include<bits/stdc++.h>
#define reg register int
#define il inline
#define fi first
#define se second
#define mk(a,b) make_pair(a,b)
#define numb (ch^'0')
using namespace std;
typedef long long ll;
template<class T>il void rd(T &x){
char ch;x=0;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*10+numb);
(fl==true)&&(x=-x);
}
template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');}
template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('
');}
namespace Miracle{
const int N=402;
const int inf=0x3f3f3f3f;
int n,l[N],r[N],c[N],tot;
int in[N][N],pre[N][N],bac[N][N],f[N][N];
ll ans=0;
int main(){
rd(n);
for(reg i=1;i<=n;++i){
rd(l[i]);rd(r[i]);
r[i]=l[i]+r[i];
c[++tot]=l[i];c[++tot]=r[i];
}
sort(c+1,c+tot+1);
tot=unique(c+1,c+tot+1)-c-1;
for(reg i=1;i<=n;++i){
l[i]=lower_bound(c+1,c+tot+1,l[i])-c;
r[i]=lower_bound(c+1,c+tot+1,r[i])-c;
// cout<<l[i]<<" and "<<r[i]<<endl;
}
for(reg i=1;i<=tot;++i){
for(reg j=i+1;j<=tot;++j){
for(reg k=1;k<=n;++k){
if(l[k]>=i&&r[k]<=j) ++in[i][j];
}
}
}
// for(reg i=1;i<=tot;++i){
// for(reg j=1;j<=tot;++j){
// cout<<i<<" "<<j<<" : "<<in[i][j]<<endl;
// }
// }
memset(pre,-inf,sizeof pre);
memset(bac,-inf,sizeof bac);
pre[1][0]=0;
for(reg i=1;i<=tot;++i){
for(reg j=0;j<=n;++j){
for(reg k=1;k<i;++k){
pre[i][j]=max(pre[i][j],pre[k][j]+in[k][i]);
if(j>=in[k][i]) pre[i][j]=max(pre[i][j],pre[k][j-in[k][i]]);
}
// cout<<" i j "<<i<<" "<<j<<" : "<<pre[i][j]<<endl;
}
}
// cout<<"---------------------------------------------------------"<<endl;
bac[tot][0]=0;
for(reg i=tot;i>=1;--i){
for(reg j=0;j<=n;++j){
for(reg k=i+1;k<=tot;++k){
bac[i][j]=max(bac[i][j],bac[k][j]+in[i][k]);
if(j>=in[i][k]) bac[i][j]=max(bac[i][j],bac[k][j-in[i][k]]);
}
// cout<<" i j "<<i<<" "<<j<<" : "<<bac[i][j]<<endl;
}
}
for(reg j=0;j<=n;++j){
ans=max(ans,(ll)min(j,pre[tot][j]));
}
cout<<ans<<endl;
for(reg l=1;l<=tot;++l){
for(reg r=l+1;r<=tot;++r){
int y=n;
for(reg x=0;x<=n;++x){
while(y&&min(x+in[l][r]+y,pre[l][x]+bac[r][y])<=min(x+in[l][r]+y-1,pre[l][x]+bac[r][y-1])) --y;
// cout<<" x y "<<x<<" "<<y<<endl;
f[l][r]=max(f[l][r],min(x+in[l][r]+y,pre[l][x]+bac[r][y]));
}
// cout<<" l r "<<l<<" "<<r<<" : "<<f[l][r]<<endl;
}
}
for(reg i=1;i<=n;++i){
int L=l[i],R=r[i];
int mx=0;
for(reg l=L;l>=1;--l){
for(reg r=R;r<=tot;++r){
mx=max(mx,f[l][r]);
}
}
cout<<mx<<endl;
}
return 0;
}
}
signed main(){
Miracle::main();
return 0;
}
/*
Author: *Miracle*
Date: 2019/4/9 10:31:40
*/
处理区间不交等问题时候，直接做要状压
不妨强制一段都颜色一致，暴力枚举转移