bzoj1151: [CTSC2007]动物园zoo

位压DP，就是五个位，表示第i个人看到的那5个动物的情况，最开始枚举有哪些动物走了，转移就很显然了

const int N = 100010, D = 31, M = 32;
struct Node {
	int Start, Love, Afraid;
	inline void Read(int n) {
		int F, L, x;
		scanf("%d%d%d", &Start, &F, &L), Start--;
		Rep(j, F) scanf("%d", &x), Afraid |= 1 << ((x - Start - 1 + n) % n);
		Rep(j, L) scanf("%d", &x), Love |= 1 << ((x - Start - 1 + n) % n);
	}
	inline bool Happy(int State) { return (State & Afraid) || ((~State) & Love); }
} Dat[N];
int n, m;
int Dp[2][M], Inc[N][M];

inline void Input() {
	scanf("%d%d", &n, &m);
	Rep(i, m) Dat[i].Read(n);
}

inline void Solve() {
	/* Init Begin */
	int Ans = 0;
	Rep(i, m)
		Rep(State, M)
			if(Dat[i].Happy(State)) Inc[Dat[i].Start][State]++;
	/* Init End*/
	
	Rep(Start, M) {
		clr(Dp, 0);
		Dp[0][Start] = Inc[0][Start];
		rep(i, 1, n + 1)
			Rep(State, M)
				Dp[i & 1][State] = max(Dp[(i - 1) & 1][((State << 1) | 1) & D], 
					Dp[(i - 1) & 1][(State << 1) & D]) + Inc[i][State];
		Ans = max(Ans, Dp[n & 1][Start]);
	}
	
	printf("%d\n", Ans);
}

int main() {
	#ifndef ONLINE_JUDGE
	SETIO("1151");
	#endif
	Input();
	Solve();
	return 0;
}