题意

题目链接

给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个区间,于是得到\(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<bits/stdc++.h>#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 <class T>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<p) break;                }                ans[i][j]=Max(ans[i][j],p);            }        }    }    for(re int i=1;i<=n;++i)    {        ccf=0;        for(re int j=1;j<=l[i];++j)            for(re int k=r[i];k<=len;++k)                ccf=Max(ccf,ans[j][k]);        printf("%d\n",ccf);    }    return 0;}