# P3622 \[APIO2007] 动物园

一、题意

你有一个 𝑁 个笼子分布呈现环形的动物园，每个笼子都关了一种动物。有 𝐶 名小朋友来动物园参观。他们喜欢和害怕某些动物，每个小朋友只能看见连续 5 个笼子，给出开始笼子的编号 E

当下面两处情况中的一种发生时，小朋友就会高兴：

1. 至少有一个他害怕的动物被移走
2. 至少有一个他喜欢的动物没被移走

求现在最多可以让多少个小朋友高兴

二、分析

每个人只能看到 5 个笼子，考虑状压每个动物被移走的状态

设 \(f[j][s]\) 表示 \([j,j+4]\) 状态为 s 时，小朋友高兴的数量

用 \(sc , l\) 两个变量记录小朋友害怕和喜欢的动物的状态（二进制）

[!NOTE]

注意处理小朋友看到的动物编号不连续，成环状的情况

	for(int i=1;i<=m;i++){cin>>E>>F>>L;int sc=0,l=0;for(int j=1;j<=F;j++){cin>>x;x=(x-E+n)%n;//环的处理，表示相对开始位置 E 的位置sc|=(1<<x);}for(int j=1;j<=L;j++){cin>>x;x=(x-E+n)%n;l|=(1<<x);}for(int j=0;j<(1<<5);j++){if((sc&(~j))||(l&j)) //1 表示留下的f[E][j]++;}}

设 \(dp[j][s]\) 表示到达动物 \(i\) 且 \([j,j+4]\) 状态为 \(s\) 时，最多能使多少小朋友高兴

\[dp[j][s]= \min (dp[j-1][(s\&15)<<1],dp[j-1][(s\&15)<<1|1])+f[j][s] \]

因为取五位二进制数的前四位较为麻烦，所以将状态反着存，取前四位就变成了取后四位，直接 \(\& 15\)

\((s\&15)<<1\) 表示 \([j-1,j+4]\) 的状态，枚举第 \(j-1\) 位为 1 还是 0

	for(int i=0;i<(1<<5);i++){memset(dp,0x8f,sizeof(dp));dp[0][i]=0;for(int j=1;j<=n;j++){for(int s=0;s<(1<<5);s++)dp[j][s]=max(dp[j-1][(s&15)<<1],dp[j-1][(s&15)<<1|1])+f[j][s];}ans=max(ans,dp[n][i]);}