[NOI2011]Noi嘉年華

題意

題目鏈接

給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中?，F在還需要知道[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;}