「APIO2007」动物园

发表于 | 分类于 | | 浏览量： 次

数据范围这么大，压个毛线啊！

传送门

洛谷P3622

BZOJ1151

题解

这题的数据范围挺大的。

但是每个小朋友只能看到连续的$5​$个围栏。

所以考虑状压DP。

$F[i][j]$表示围栏$i,i+1,i+2,i+3,i+4$的状态为$j$时，站在前$i$个位置中的小朋友最多有几个开心。

转移方程还是比较容易就能写出来的，但是由于这是一个环，相接的部分比较难搞。

由于$2^5=32$还是比较小的，直接暴力枚举前5个位置的状态，然后刷多次DP就好了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10005;
int n,C,F[maxn][35],W[maxn][35],ans;
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
int main()
{
	n=read();C=read();
	for(int i=1;i<=C;i++)
	{
		int E=read(),F=read(),L=read(),S1=0,S2=0;
		for(int j=1;j<=F;j++)
			S1|=(1<<((read()-E+n)%n));
		for(int j=1;j<=L;j++)
			S2|=(1<<((read()-E+n)%n));
		for(int j=0;j<32;j++)
			if((j&S2)||((~j)&S1))
				W[E][j]++;
	}
	for(int s=0;s<32;s++)
	{
		memset(F[0],192,sizeof(F[0]));
		F[0][s]=0;
		for(int i=1;i<=n;i++)
			for(int j=0;j<32;j++)
				F[i][j]=max(F[i-1][(j&15)<<1],F[i-1][(j&15)<<1|1])+W[i][j];
		if(F[n][s]>ans) ans=F[n][s];
	}
	printf("%d\n",ans);
	return 0;
}