P1973 [NOI2011]Noi嘉年华

传送门

首先可以把时间区间离散化

然后求出 $cnt[l][r]$ 表示完全在时间 $[l,r]$ 之内的活动数量

设 $f[i][j]$ 表示当前考虑到时间 $i$，第一个会场活动数量为 $j$ 时，另一个会场的最大活动数量

这个转移直接枚举上一个时间分界线 $k$， $f[i][j]=max(f[k][j]+cnt[k][i])$ 表示 $[k,i]$ 时间的活动给第二个会场

$f[i][j]=max(f[k][j-cnt[k][i]])$ 表示 $[k,i]$ 时间的活动给第一个会场

这样第一问没有限制的最大数量就可以求出

考虑强制选某个的情况，那么我们可以把时间分成三部分，左右两边和中间强制选的一段时间

左边的贡献可以用 $f$ 求出，同理我们考虑设 $g[i][j]$ 表示当前从 $i$ 考虑到结束，第一个会场活动数量为 $j$ 时，另一个会场的最大活动数量

那么右边的贡献也可以求出，考虑设 $h[i][j]$ 表示 $[i,j]$ 的活动强制选时的最大答案

考虑枚举左右两边的 $j$ 分别为 $x,y$，即第一个会场活动数量

那么有 $h[L][R]=min(x+y+cnt[L][R],f[L][x]+g[R][y])$，这样总复杂度是 $n^4$ 的，考虑关于单调性的优化

发现转移时，对于某个 $x=a$，此时 $y=b$ 最优，那么对于 $x=a+1$，最优点 $y'<=b$

因为第一个会场活动多了第二个就少了，答案就会越来越小

所以枚举 $x$ 的时候动态维护 $y$ 指针即可，复杂度 $O(n^3)$

注意最后每一个的答案是枚举 $L<=a[i].l,R>=a[i].r$ 中的 $h[L][R]$ 取 $max$，而不是直接 $h[a[i].l][a[i].r]$

（$a[i].l,a[i].r$ 表示第 $i$ 个活动的时间区间）

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=,INF=1e9+;

int n,d[N],m;

struct act{

    int l,r;

}a[N];

int cnt[N][N],f[N][N],g[N][N],h[N][N];

inline int calc(int L,int R,int x,int y) { return min(x+y+cnt[L][R] , f[L][x]+g[R][y]); }

int main()

{

    n=read();

    for(int i=;i<=n;i++)

    {

        a[i].l=read(),a[i].r=a[i].l+read();

        d[i]=a[i].l,d[n+i]=a[i].r;

    }

    sort(d+,d+*n+); m=unique(d+,d+*n+)-d-;

    for(int i=;i<=n;i++)

    {

        a[i].l=lower_bound(d+,d+m+,a[i].l)-d;

        a[i].r=lower_bound(d+,d+m+,a[i].r)-d;

    }

    for(int l=;l<=m;l++)

        for(int r=l+;r<=m;r++)

            for(int i=;i<=n;i++)

                    cnt[l][r]+=(a[i].l>=l&&a[i].r<=r);

    for(int i=;i<=m;i++)

        for(int j=;j<=n;j++) f[i][j]=g[i][j]=-INF;

    for(int i=;i<=m;i++)

        for(int j=;j<=cnt[][i];j++)

            for(int k=;k<i;k++)

            {

                f[i][j]=max(f[i][j],f[k][j]+cnt[k][i]);

                if(j>=cnt[k][i]) f[i][j]=max(f[i][j],f[k][j-cnt[k][i]]);

            }

    for(int i=m-;i>=;i--)

        for(int j=;j<=cnt[i][m];j++)

            for(int k=i+;k<=m;k++)

            {

                g[i][j]=max(g[i][j],g[k][j]+cnt[i][k]);

                if(j>=cnt[i][k]) g[i][j]=max(g[i][j],g[k][j-cnt[i][k]]);

            }

    // min( x+y+cnt[L][R] , f[L][x]+f[R][y] )

    for(int L=;L<=m;L++)

        for(int R=L+;R<=m;R++)

            for(int x=,y=n;x<=n;x++)

            {

                while(y&&calc(L,R,x,y)<=calc(L,R,x,y-)) y--;

                h[L][R]=max(h[L][R],calc(L,R,x,y));

            }

    int ans=; for(int i=;i<=n;i++) ans=max(ans,min(f[m][i],i));

    printf("%d\n",ans);

    for(int i=;i<=n;i++)

    {

        ans=;

        for(int L=;L<=a[i].l;L++)

            for(int R=a[i].r;R<=m;R++) ans=max(ans,h[L][R]);

        printf("%d\n",ans);

    }

    return ;

}

巴特西

P1973 [NOI2011]Noi嘉年华

最新文章

热门文章