洛谷3622 [APIO2007]动物园

题意

动物园的笼子环形排列，每个小朋友能看到从站的位置开始往后共 $5$ 个笼子的动物，每个小朋友都有喜欢和害怕的动物。可以移走一部分笼子。

定义每个小朋友是开心的，当且仅当下列条件之一满足：

1. 在视线范围内至少有一个喜欢的动物没被移走。
2. 在视线范围内至少有一个害怕的动物被移走。

求最优方案，使得开心的小朋友尽可能多。

其中动物数 $N\le 10000$ ，小朋友个数 $C\le 50000$ 。

题解

动物数多达 $10000$ ，直接状压显然是不行的。但是每个小朋友只能看到 $5$ 个动物，所以可以对每个位置看到动物的情况进行状压，用 $1$ 代表移走，$0$ 代表没移走。

先预处理出来每个位置上看到动物情况会有多少小朋友是开心的（因为一个位置有可能有多个人所以不能用bool），将第 $i$ 个位置状态为 $j$ 的开心的小朋友数保存为 $\text{s}[i][j]$ 。

预处理的方法为先得到当前小朋友害怕的动物和喜欢的动物的状态 $x$ 和 $y$，然后枚举移动状态 $j$ ，小朋友开心的条件既可以转化为：

$$(x\&j) || (y\& \sim j)$$

然后dp。方程式为：

$$\text{f}[i][j]=\max{(\text{f}[i-1][(j\&15)<<1],\text{f}[i-1][(j\&15)<<1|1])}+\text{s}[i][j]$$

用 $15$ 的原因是其二进制为 $01111$ ，刚好可以取后四位，然后左移后就可以枚举上一步的状态了。

因为是一个环，所以需要先枚举前 $5$ 个状态，最后与枚举的相同的状态才可以计入答案。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int s[10005][35],f[10005][35],n,m,a,b,c,ans;

int main()
{
    n=read(); m=read();
    for (int i=1;i<=m;i++)
    {
        int x=0,y=0;
        a=read(); b=read(); c=read();
        for (int j=1;j<=b;j++) x|=1<<((read()-a+n)%n);
        for (int j=1;j<=c;j++) y|=1<<((read()-a+n)%n);
        for (int j=0;j<32;j++) s[a][j]+=((x&j) || (y&~j));
    }
    for (int i=0;i<32;i++)
    {
        memset(f,-0x3f,sizeof(f));
        f[0][i]=0;
        for (int j=1;j<=n;j++)
            for (int k=0;k<32;k++)
                f[j][k]=max(f[j-1][(k&15)<<1],f[j-1][(k&15)<<1|1])+s[j][k];
        ans=max(ans,f[n][i]);
    }
    printf("%d",ans);
    return 0;
}