自动搬运

查看原文

来自洛谷，原作者为

	Rayment **

搬运于2025-08-24 21:50:53，当前版本为作者最后更新于2018-02-01 17:24:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

这是一道状压DP的好题……

首先可以注意到每个小朋友只能看见5个围栏，数据范围很小，其次由于小朋友喜欢和讨厌的动物都是他能看到的，那么这个小朋友是否满意就只与这五格围栏有关，那么可以考虑状态压缩。

考虑到可能小朋友看见的围栏范围可能相同，那么我们可以预处理num[pos][s]，表示从第pos个围栏开始的五个围栏状态为s时，会有多少个小朋友满意。 定义状态f[i][s]表示枚举到第i个围栏且[i,i+5]的围栏移走状态为s时的最多满意人数。则f[i][s]可以由第i-1个围栏移走和不移走两种状态转移得来：

$ f[i][s]=\max{(f[i-1][(s\&15)<<1],f[i-1][(s\&15)<<1|1])}+num[i][s] $

其次要注意的是在dp之前先枚举前五个的状态state，因为围栏是一个环，最后枚举第n+1个围栏时，其实就相当于又回到了第一个围栏，那么此时必须满足s=state才是有效状态，更新答案。

时间复杂度$O(2^{10}\times n)$

Code

#include <iostream>
#include <cstring>
#include <cstdio>
#define check(st) ((st&l)||(~st&d))
using namespace std;
template <typename Tp> inline void read(Tp &x)
{
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
}
const int maxn=50010;
int n,m,ans,f[maxn][40],num[maxn][40];
inline int max(int x,int y){return x>y?x:y;}
void input()
{
	int a,b,c,l,d,t;
	read(n);read(m);
	for(int i=1;i<=m;i++)
	{
		read(a);read(b);read(c);
		l=d=0;
		for(int j=1;j<=b;j++)
		  {read(t);t=(t-a+n)%n;l|=1<<t;}
		for(int j=1;j<=c;j++)
		  {read(t);t=(t-a+n)%n;d|=1<<t;}
		for(int j=0;j<32;j++)
		  if(check(j))
		    num[a][j]++;
	}
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	#endif
	input();
	for(int i=0;i<32;i++)
	{
		memset(f[0],128,sizeof(f[0]));//设一个极小值即可
		f[0][i]=0;
		for(int j=1;j<=n;j++)
		  for(int s=0;s<32;s++)
		    f[j][s]=max(f[j-1][(s&15)<<1],f[j-1][(s&15)<<1|1])+num[j][s];
		if(ans<f[n][i])
		  ans=f[n][i];
	}
	printf("%d\n",ans);
	return 0;
}