动物园zoo
题目大意：https://www.lydsy.com/JudgeOnline/problem.php?id=1151
题解：
我们发现每个点只会往右延伸$5$个，这个数非常小。
再加上每个动物只有选和不选，很容易想到把每个点后面$5$个给状压到一起。
想到这里就好办了，随便弄个数组搞一搞就好。
代码：
#include <bits/stdc++.h>
#define N 50010
using namespace std;
int n, c, f[N][35], bu[N][35], last, ans;
char *p1, *p2, buf[100000];
#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )
int rd() {
int x = 0, f = 1;
char c = nc();
while (c < 48) {
if (c == '-')
f = -1;
c = nc();
}
while (c > 47) {
x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();
}
return x * f;
}
int main() {
int n = rd(), c = rd();
for (int i = 1; i <= c; i ++ ) {
int a = rd(), l1 = rd(), l2 = rd();
int t1 = 0, t2 = 0;
for (int j = 1; j <= l1; j ++ ) {
t1 |= 1 << ((rd() - a + n) % n);
}
for (int j = 1; j <= l2; j ++ ) {
t2 |= 1 << ((rd() - a + n) % n);
}
for (int j = 0; j < 32; j ++ ) {
if ((j & t1) || (~j & t2)) {
bu[a][j] ++ ;
}
}
}
last = 0;
for (int j = 0; j < 32; j ++ ) {
memset(f[0], 0xef, 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]) + bu[i][k];
}
}
ans = max(ans, f[n][j]);
}
cout << ans << endl ;
return 0;
}
小结：发现前i个只跟后面5个的01情况有关，我们就直接存起来f[i][S]就好。