Description:

一个长为 $N$ 环形的动物园，个 $M$ 小朋友，每个小朋友能看到固定的连续的五个笼子，每个小朋友有喜欢的和不喜欢的动物，一个小朋友高兴当且仅当有至少一个他喜欢的动物没被移走或者至少一个他喜欢的动物被移走了，求通过移走一些动物使得高兴的小朋友尽量多。

$10 \le N \le 10000$ $1 \le M \le 50000$

Solution:

每个人只有五个笼子和他有关，不难想到状压， $f[i][j]$ 表示从 $i$ 开始连续五个笼子内动物的移走状态是 $j$ ，预处理出 $g[i][j]$ 数组表示从 $i$ 开始状态为 $j$ 的状态的价值，每次枚举下一个选或不选即可。

注意由于是环，而状态定义与后四个状态有关，所以开始和结尾绕回来的部分必须相同，因此枚举前四个的选择状态 $k$ ， $f[0][k<<1] = 0$ ，其余赋为 $-INF$ 。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 10010

#define MAXM 50010 

int p[MAXM],l[MAXM],h[MAXM];

int g[MAXN][1 << 5];

int f[MAXN][1 << 5];

int main()

{

	scanf("%d%d",&n,&m);

	int x,y,a;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d",&p[i]);

		scanf("%d%d",&l[i],&h[i]);x = y = 0; 

		for(int k = 1;k <= l[i];++k){scanf("%d",&a);x |= (1 << ((a + n - p[i]) % n));}

		for(int k = 1;k <= h[i];++k){scanf("%d",&a);y |= (1 << ((a + n - p[i]) % n));}

		for(int k = 0;k < (1 << 5);++k)if((k & x) || ((31 ^ k) & y)){++g[p[i]][k];}

	}

	int ans = 0;

	for(int k = 0;k < (1 << 4);++k)

	{

		memset(f,0xc0,sizeof(f));

		f[0][k << 1] = 0;

		for(int i = 1;i <= n;++i)

		{

			for(int t = 0;t < (1 << 5);++t)

			{

				f[i][t] = max(f[i - 1][(t & 15) << 1],f[i - 1][(t & 15) << 1 | 1]) + g[i][t];

			}

		}

		ans = max(ans,max(f[n][k << 1],f[n][k << 1 | 1]));

	}

	cout << ans << endl;

	return 0;

}