@ysner
2018-05-19T15:16:43.000000Z
字数 1048
阅读 1804
状压DP
DP
注意到每个小朋友只能看到个动物,可以状压。
我们可以对每个小朋友预处理一下他面对每种状态会不会满意。
然后就可枚举动物数和当前状态进行状压。
有点绕脑的是这是个环。
我们在开始时规定号位(即号位)的某一状态可以转移,最后只统计号位上这一状态的答案即可。
#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()
{
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;
}