题意

给n个区间\((n\leq 200)\)，选择其中一些并分成两部分，要求两部分的区间分别并起来之后两者没有交集，求此时含区间数量少的一部分数量最大为多少。另外，对于每个区间，求出它必须选时的答案

思路

神奇的DP（为什么我有网络流的思路的题都是DP啊qwq）

先离散化自不必说，设离散化后最远覆盖到了len位置

\(cnt[i][j]\):完整的处于\([i,j]\)里的区间个数

\(pre[i][j]\):在区间\([1,i]\)中，A选择了j个区间时，B最多可以选择的区间个数

\(las[i][j]\):在区间\([i,len]\)中，A选择了j个区间时，B最多可以选择的区间个数

对于完整的一块，我们可以将它扔在A或者B，这就成了我们的决策，于是得到了转移方程：

\(pre[i][j]=max(pre[k][j]+cnt[k][j],pre[k][j-cnt[k][j]])\)//分别代表将\([k,j]\)这一块扔到B或者A（las同理）

于是\(ans1=max(min(i,pre[len][i]))\)//前者是A中的区间数，后者是此时的B中的区间数，两者需要取min

接下来处理强行选择c号区间的情况

对于每一个c，枚举一个块\([i,j]\)，这个块必须选，且这个块包含了c号区间，假设它在A中。现在还需要知道\([1,i]\)和\([j,len]\)这两部分怎么选择，假设在这两部分中A分别选择了x,y个区间，由于对于每一个c都要跑一次，得到一个\(n^5\)的方法：

\(ans=max(min(x+y+cnt[i][j],pre[i][x]+las[j][y]))\)//前为A，后为B

一个显然的优化就是，我们这样做一次就可以把所有的情况处理出来（上面的四重循环与c无关），我们设\(ans[i][j]\)表示强制选择\([i,j]\)时的答案，复杂度降至\(n^4\)

另外，当x增大时，如果y也随之增大，此时\(pre[i][x]+las[j][y]\)显然只会变小，此时无法更新答案，所以y只能减小，即y随着x增大而减小。我们在无法更新答案的时候将y减1即可

Code

#include
    
     #define N 405 #define re register#define Max(x,y) ((x)>(y) ? (x):(y))using namespace std;int n,ccf,l[N],r[N],cnt[N][N];int pre[N][N],las[N][N];//cnt[i][j]表示完全包含在[i,j]的区间个数 //pre[i][j]表示在时间[1,i],A场选择j个区间时B场选择最多的区间个数 int ans[N][N];//[i,j]区间必选时的答案 int b[N<<1],len;template 
     
      void read(T &x){    char c;int sign=1;    while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;    while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;}int main(){    read(n);    for(re int i=1;i<=n;++i)    {        int t;        read(l[i]);read(t);        r[i]=l[i]+t;        b[++len]=l[i];        b[++len]=r[i];    }    sort(b+1,b+len+1);    len=unique(b+1,b+len+1)-b-1;    for(re int i=1;i<=n;++i)    {        l[i]=lower_bound(b+1,b+len+1,l[i])-b;        r[i]=lower_bound(b+1,b+len+1,r[i])-b;    }    for(re int i=1;i<=len;++i)        for(re int j=i;j<=len;++j)            for(re int k=1;k<=n;++k)                if(i<=l[k]&&r[k]<=j) cnt[i][j]++;    memset(pre,-50,sizeof(pre));    memset(las,-50,sizeof(las));    for(re int i=1;i<=len;++i)    {        pre[i][0]=cnt[1][i];        for(re int j=1;j<=cnt[1][i];++j)            for(re int k=1;k<=i;++k)            {                pre[i][j]=Max(pre[i][j],pre[k][j]+cnt[k][i]);//[k,i]分给B                 if(j>=cnt[k][i]) pre[i][j]=Max(pre[i][j],pre[k][j-cnt[k][i]]);//[k,i]分给A             }    }    for(re int i=len;i>=1;--i)    {        las[i][0]=cnt[i][len];        for(re int j=1;j<=cnt[i][len];++j)            for(re int k=i;k<=len;++k)            {                las[i][j]=Max(las[i][j],las[k][j]+cnt[i][k]);                if(j>=cnt[i][k]) las[i][j]=Max(las[i][j],las[k][j-cnt[i][k]]);            }    }    ccf=0;    for(re int i=0;i<=n;++i) ccf=Max(ccf,min(pre[len][i],i));    printf("%d\n",ccf);    for(re int i=1;i<=len;++i)    {        for(re int j=1;j<=len;++j)        {            ans[i][j]=-10000;            int y=cnt[j][len];            for(re int x=0;x<=cnt[1][i];++x)//A在[1,i]区间选择了x个             {                int p,q;                for(;y>=0;--y)                {                    p=min(x+y+cnt[i][j],pre[i][x]+las[j][y]);                    if(!y) break;                    q=min(x+y-1+cnt[i][j],pre[i][x]+las[j][y-1]);                    if(q