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=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
    return x*f;
}
const int N=507,INF=1e9+7;
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=1;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+1,d+2*n+1); m=unique(d+1,d+2*n+1)-d-1;
    for(int i=1;i<=n;i++)
    {
        a[i].l=lower_bound(d+1,d+m+1,a[i].l)-d;
        a[i].r=lower_bound(d+1,d+m+1,a[i].r)-d;
    }
    for(int l=1;l<=m;l++)
        for(int r=l+1;r<=m;r++)
            for(int i=1;i<=n;i++)
                    cnt[l][r]+=(a[i].l>=l&&a[i].r<=r);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++) f[i][j]=g[i][j]=-INF;
    for(int i=1;i<=m;i++)
        for(int j=0;j<=cnt[1][i];j++)
            for(int k=0;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-1;i>=1;i--)
        for(int j=0;j<=cnt[i][m];j++)
            for(int k=i+1;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=1;L<=m;L++)
        for(int R=L+1;R<=m;R++)
            for(int x=0,y=n;x<=n;x++)
            {
                while(y&&calc(L,R,x,y)<=calc(L,R,x,y-1)) y--;
                h[L][R]=max(h[L][R],calc(L,R,x,y));
            }
    int ans=0; for(int i=0;i<=n;i++) ans=max(ans,min(f[m][i],i));
    printf("%d\n",ans);
    for(int i=1;i<=n;i++)
    {
        ans=0;
        for(int L=1;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 0;
}

View Code

P1973 [NOI2011]Noi嘉年华

推荐阅读