【BZOJ2436】NOI嘉年华（NOI2011）-区间DP+决策单调性优化

测试地址：NOI嘉年华
做法：本题需要用到区间DP+决策单调性优化。
因为两个会场不能同时有活动，不难想到活动一定会排成，在A会场一段，又在B会场一段，这样交替的形式。很快想到区间DP来决策每一段是在A会场还是B会场。
我们首先将所有时刻离散化，接着为了转移方便，我们显然应该处理出 num(i,j) $num(i,j)$：时刻 i,j $i,j$之间的活动数量。这个直接 O(n3) $O(n^3)$预处理即可。然后我们令 lft(i,j) $lft(i,j)$为时刻 i $i$前，A会场选了 j $j$个活动时，B会场最多选的活动数量，这个可以从以下这些状态转移而来：
枚举新的一段 [k,i](1≤k<i) $[k,i](1\le k<i)$，那么：
如果这段不选，则从 lft(i−1,j) $lft(i-1,j)$转移；
如果这段在A会场，则从 lft(k,j)+num(k,i) $lft(k,j)+num(k,i)$转移；
如果这段在B会场，则从 lft(k,j−num(k,i)) $lft(k,j-num(k,i))$转移。
这样第一问就解决了，答案显然为 max{min(lft(end,i),i)} $max\{min(lft(end,i),i)\}$。
问题是第二问，我们要求 g(i,j) $g(i,j)$： [i,j] $[i,j]$这一段内的活动必须选的最大答案，那么我们应该处理 i $i$左边和 j $j$右边的部分，这就是我们上面求出的 lft $lft$，只需再从后往前类似求出一个 rht $rht$来就好了。然后我们枚举左边A会场选的活动数量 x $x$，右边A会场选的活动数量 y $y$，于是有：
g(i,j)=max{min(x+y+num(i,j),lft(i,x)+rht(j,y))} $g(i,j)=max\{min(x+y+num(i,j),lft(i,x)+rht(j,y))\}$
但是直接枚举是 O(n4) $O(n^4)$的，注意到当 x $x$增大时，方案要变得更优， y $y$必须要更小，而这个东西始终是一个单峰函数，所以我们用一个指针来枚举 y $y$即可，时间复杂度为 O(n3) $O(n^3)$。
以下是本人代码：

#include <bits/stdc++.h>
using namespace std;
const int inf=1000000000;
int n,tot,s[410],t[410];
int num[410][410]={0},lft[410][410]={0},rht[410][410]={0},g[410][410]={0};
struct forsort
{
    int id,val;
}f[410];

bool cmpf(forsort a,forsort b)
{
    return a.val<b.val;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int s,t;
        scanf("%d%d",&s,&t);
        f[2*i-1].id=2*i-1,f[2*i-1].val=s;
        f[2*i].id=2*i,f[2*i].val=s+t;
    }
    sort(f+1,f+2*n+1,cmpf);

    tot=0;
    for(int i=1;i<=2*n;i++)
    {
        if (!tot||f[i].val!=f[i-1].val) tot++;
        if (f[i].id%2) s[(f[i].id+1)>>1]=tot;
        else t[f[i].id>>1]=tot;
    }

    for(int i=1;i<=tot;i++)
        for(int j=i;j<=tot;j++)
        {
            num[i][j]=0;
            for(int k=1;k<=n;k++)
                if (s[k]>=i&&t[k]<=j) num[i][j]++;
        }

    for(int i=1;i<=tot;i++)
        for(int j=0;j<=n;j++)
        {
            if (j>num[1][i]) {lft[i][j]=-inf;continue;}
            lft[i][j]=lft[i-1][j];
            for(int k=1;k<i;k++)
            {
                lft[i][j]=max(lft[i][j],lft[k][j]+num[k][i]);
                if (num[k][i]<=j) lft[i][j]=max(lft[i][j],lft[k][j-num[k][i]]);
            }
        }

    for(int i=tot;i>=1;i--)
        for(int j=0;j<=n;j++)
        {
            if (j>num[i][tot]) {rht[i][j]=-inf;continue;}
            rht[i][j]=rht[i+1][j];
            for(int k=i+1;k<=tot;k++)
            {
                rht[i][j]=max(rht[i][j],rht[k][j]+num[i][k]);
                if (num[i][k]<=j) rht[i][j]=max(rht[i][j],rht[k][j-num[i][k]]);
            }
        }

    int nowans=0;
    for(int i=0;i<=n;i++)
        nowans=max(nowans,min(lft[tot][i],i));
    printf("%d\n",nowans);

    for(int i=1;i<=tot;i++)
        for(int j=i;j<=tot;j++)
        {
            int y=n;
            g[i][j]=0;
            for(int x=0;x<=n;x++)
            {
                while(y&&min(x+y+num[i][j],lft[i][x]+rht[j][y])<=min(x+(y-1)+num[i][j],lft[i][x]+rht[j][y-1])) y--; 
                g[i][j]=max(g[i][j],min(x+y+num[i][j],lft[i][x]+rht[j][y]));
            }
        }

    for(int i=1;i<=n;i++)
    {
        int ans=0;
        for(int j=1;j<=s[i];j++)
            for(int k=t[i];k<=tot;k++)
                ans=max(ans,g[j][k]);
        printf("%d\n",ans);
    }

    return 0;
}