题意分析

这是一道状压\(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
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #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 registerusing namespace std;template
                   
                    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<