2018.09.08 bzoj1151: [CTSC2007]动物园zoo（状压dp）

传送门

状压dp好题啊。

可以发现这道题的状压只用压缩5位。

f[i][j]表示当前在第i个位置状态为j的最优值。

显然可以由f[i-1]更新过来。

因此只用预处理在第i个位置状态为j时有多少个小朋友高兴就行了。

代码：

#include<bits/stdc++.h>#define N 50005using namespace std;int n,c,f[N][35],cal[N][35],las,ans=0;inline int read(){    int ans=0;    char ch=getchar();    while(!isdigit(ch))ch=getchar();    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();    return ans;}inline int max(int a,int b){return a>b?a:b;}int main(){    n=read(),c=read();    for(int i=1;i<=c;++i){        int a=read(),b=read(),c=read(),tmp1=0,tmp2=0;        for(int j=1;j<=b;++j)tmp1|=1<<((read()-a+n)%n);        for(int j=1;j<=c;++j)tmp2|=1<<((read()-a+n)%n);        for(int j=0;j<32;++j)if((j&tmp1)||(~j&tmp2))++cal[a][j];    }    las=15;    for(int j=0;j<32;++j){        memset(f[0],-0x3f,sizeof(f[0]));        f[0][j]=0;        for(int i=1;i<=n;++i)for(int k=0;k<32;++k)                f[i][k]=max(f[i-1][(k&15)<<1],f[i-1][(k&15)<<1|1])+cal[i][k];        ans=max(ans,f[n][j]);    }    cout<<ans;    return 0;}