题解 P3622 【[APIO2007]动物园】

· · 题解

Solution

这是一道状压DP的好题……

首先可以注意到每个小朋友只能看见5个围栏，数据范围很小，其次由于小朋友喜欢和讨厌的动物都是他能看到的，那么这个小朋友是否满意就只与这五格围栏有关，那么可以考虑状态压缩。

考虑到可能小朋友看见的围栏范围可能相同，那么我们可以预处理num[pos][s]，表示从第pos个围栏开始的五个围栏状态为s时，会有多少个小朋友满意。 定义状态f[i][s]表示枚举到第i个围栏且[i,i+5]的围栏移走状态为s时的最多满意人数。则f[i][s]可以由第i-1个围栏移走和不移走两种状态转移得来：

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

其次要注意的是在dp之前先枚举前五个的状态state，因为围栏是一个环，最后枚举第n+1个围栏时，其实就相当于又回到了第一个围栏，那么此时必须满足s=state才是有效状态，更新答案。

时间复杂度O(2^{10}\times n)

Code

#include <iostream>
#include <cstring>
#include <cstdio>
#define check(st) ((st&l)||(~st&d))
using namespace std;
template <typename Tp> inline void read(Tp &x)
{
    x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
}
const int maxn=50010;
int n,m,ans,f[maxn][40],num[maxn][40];
inline int max(int x,int y){return x>y?x:y;}
void input()
{
    int a,b,c,l,d,t;
    read(n);read(m);
    for(int i=1;i<=m;i++)
    {
        read(a);read(b);read(c);
        l=d=0;
        for(int j=1;j<=b;j++)
          {read(t);t=(t-a+n)%n;l|=1<<t;}
        for(int j=1;j<=c;j++)
          {read(t);t=(t-a+n)%n;d|=1<<t;}
        for(int j=0;j<32;j++)
          if(check(j))
            num[a][j]++;
    }
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    input();
    for(int i=0;i<32;i++)
    {
        memset(f[0],128,sizeof(f[0]));//设一个极小值即可
        f[0][i]=0;
        for(int j=1;j<=n;j++)
          for(int s=0;s<32;s++)
            f[j][s]=max(f[j-1][(s&15)<<1],f[j-1][(s&15)<<1|1])+num[j][s];
        if(ans<f[n][i])
          ans=f[n][i];
    }
    printf("%d\n",ans);
    return 0;
}