题目链接
题意分析
这是一道状压\(DP\)的题
一个人只可以欣赏到\(5\)只动物 显然可以状压
我们用\(dp[i][j]\)表示当前\([i,i+4]\)中这\(5\)只动物的状态\(j\) 在或者不在
最多可以满意的小朋友数
\(num[i][j]\)表示当前\([i,i+4]\)中这\(5\)只动物的状态\(j\) 在或者不在
可以满意的小朋友数
那么就是
\[dp[i][j]=max(dp[i-1][(j\&15)<<1],dp[i-1][(j\&15)<<1|1])+num[i][j]\]
其中首先按位与\(15\)是因为
按照关系\(i\)同\(i-1\)个人是共同欣赏\(4\)只动物的
所以我们就提出来
那么前驱状态就只有两种
然后预处理出\(num\)之后 正常转移就可以了
同时需要注意的是
由于是一个环
所以最后的状态要等同于开始的状态
所以我们还需要枚举一个状态
CODE:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<list>
#include<set>
#include<deque>
#include<vector>
#include<ctime>
#define ll long long
#define inf 0x7fffffff
#define N 50008
#define IL inline
#define M 10011
#define D 50
#define ull unsigned long long
#define R register
using namespace std;
template<typename T>IL void read(T &_)
{
T __=0,___=1;char ____=getchar();
while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();}
while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();}
_=___ ? __:-__;
}
/*-------------OI使我快乐-------------*/
int n,m,ans;
int dp[M][50],num[M][50];
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n);read(m);
for(R int i=1,x,y,z,cdy,wzy;i<=m;++i)
{
cdy=wzy=0;
read(x);read(y);read(z);
for(R int j=1,tmp;j<=y;++j)
{
read(tmp);
tmp=(tmp-x+n)%n;
cdy|=(1<<tmp);
}
for(R int j=1,tmp;j<=z;++j)
{
read(tmp);
tmp=(tmp-x+n)%n;
wzy|=(1<<tmp);
}
for(R int j=0;j<32;++j)
{
if((cdy&j)||((~j)&wzy))
num[x][j]++;
}
}
for(R int x=0;x<32;++x)
{
memset(dp[0],-0x3f,sizeof dp[0]);
dp[0][x]=0;
for(R int i=1;i<=n;++i)
for(R int j=0;j<32;++j)
dp[i][j]=max(dp[i-1][(j&15)<<1],dp[i-1][(j&15)<<1|1])+num[i][j];
ans=max(ans,dp[n][x]);
}
printf("%d\n",ans);
// fclose(stdin);
// fclose(stdout);
return 0;
}