把若干区间分成两个集合（可以有的区间不放在任意集合中），使得任意的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
      
       #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
       
        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
        
         il void output(T x){
     if(x/10)output(x/10);putchar(x%10+'0');}template
         
          il void ot(T x){
     if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
          
           il void prt(T a[],int st,int nd){
     for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}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<
           
            <<" and "<
            
             <
             
              =i&&r[k]<=j) ++in[i][j]; } } }// for(reg i=1;i<=tot;++i){// for(reg j=1;j<=tot;++j){// cout<
              <<" "<
               
                <<" : "<
                
                 <
                 
                  =in[k][i]) pre[i][j]=max(pre[i][j],pre[k][j-in[k][i]]); }// cout<<" i j "<
                  <<" "<
                   
                    <<" : "<
                    
                     <
                     
                      =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 "<
                      <<" "<
                       
                        <<" : "<
                        
                         <
                         
                          =1;--l){ for(reg r=R;r<=tot;++r){ mx=max(mx,f[l][r]); } } cout<
                          
                           <
                          
                         
                        
                       
                     
                    
                   
                 
                
               
             
            
           
          
         
        
       
      

 处理区间不交等问题时候，直接做要状压

不妨强制一段都颜色一致，暴力枚举转移