好写 爱写 没事干 所以有了这篇题解
洛谷P3622 [APIO2007] 动物园 题解
题目说的挺繁琐，其实就传达了一个很简单的信息：
\(n\)个动物，\(c\)个小孩，每个小孩能看到\(5\)个动物（所在的位置）\(E\)到\(E+4\)，有\(F\)个害怕的动物，\(L\)个喜欢的动物。如果视野中有至少一个喜欢的动物，或者讨厌的动物被移走至少一个，他就会高兴。你可以任意移走动物，求最多有几个小孩高兴。
由于每个视野固定长度为\(5\)，所以只要状压每五个动物被移走的状态即可，枚举范围为\(0\) ~ \(2^5-1\)，即\(0\) ~ \(31\)。
输入的时候做好初始化工作，得到数组\(num[N][S]\)，表示从\(N\)开始5个动物在\(S\)状态下高兴的孩子数。
然后整个循环遍历一遍，状态转移方程为：
\[f[i][k] = max (f[i-1] [(j\And15)<<1],f[i-1][(j\And15)<<1|1]+num[i][k] ) \]还有就是：
定义局部变量一定要记得初始化啊啊啊啊啊啊！！！
咳 下面是代码：
**code**
/*函数内定义变量一定要初始化啊啊啊啊啊啊*/
#include<bits/stdc++.h>
#define fo(x,y,z) for(int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
inline int qr()
{
char ch=getchar();int x=0,f=1;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
#define qr qr()
const int Ratio=0;
const int N=50005;
const int maxx=INT_MAX;
const double eps=1e-8;
int n,m,ans;
#define check(st) ((st&l)||(~st&d))
int num[N][50],zl[N][50];
int main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
n=qr,m=qr;
ans=-maxx;
fo(i,1,m)
{
int a=qr,b=qr,c=qr,l=0,r=0,d=0;//***
fo(j,1,b)
d=qr,d=(d-a+n)%n,l|=1<<d;
fo(j,1,c)
d=qr,d=(d-a+n)%n,r|=1<<d;
fo(j,0,31)
if((j&l)||(~j&r))
num[a][j]++;//第a个点开始状态为j满足的小孩的个数
}
fo(i,0,31)//每个人只能看到5动物 枚举状态
{
fo(j,0,35)
zl[0][j]=-maxx;
zl[0][i]=0;
fo(j,1,n)//遍历以n为起点向下五个状态的情况
fo(k,0,31)
zl[j][k]=max(zl[j-1][(k&15)<<1],zl[j-1][(k&15)<<1|1])+num[j][k];
ans=max(ans,zl[n][i]);
}
printf("%d\n",ans);
return Ratio;
}
\(End.\)
彩蛋
