Lougu P3622 [APIO2007]动物园

题目大意 ：

一群小盆友到动物园来玩，有些动物是有些小盆友喜欢的，但是有些动物是有些小盆友不喜欢的，请求出移去若干个动物（至少剩下一个）使得高兴φ(゜▽゜*)♪的小盆友最多（当一个小盆友喜欢的动物没有被你移走或讨厌的动物被你移走时[当然是要看得见的动物]，他是高兴的）

这题其实就是一个奇怪的状压dp

为什么奇怪呢?是因为他的状态很奇怪

本来是想直接枚举每个动物移走或不移走，用0、1来表示，再进行状压

但是小盆友的数量很多，导致可能会TLE

所以我们发现每个小盆友的视线（眼瞎？）都很小，那么我们就可以用\(f[s][i]\)表示当枚举到第\(i\)个栅栏时，第\(i\)到\(i+4\)个栅栏移走的状态为\((s)_2\)时，我们开心，呸，高兴的小盆友的数量

但是我们又发现，每次转移一次方程的时候都要求一遍当前状态为\(s\)时的开心的小盆友数量。每次都会重复算好几遍，又要T？？？ 不过好像读入的时候一边读入一边计算就好了。

然后我们的答案就只要取\(Max({f[n][(00000)_2],f[n][(00001)_2],...,f[n][(11111)_2]})\)就好了

来看一下转移方程：

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

\(f[i][s]\)从第\(i-1\)个栅栏移走或是不移走的时候转移过来

代码还有点锅，先咕了