状压DP

wangbinfeng · 2021-09-13 20:50:07 · 算法·理论

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    char c;
    int ret=0;
    for(c=getchar();c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar())ret=ret*10+c-'0';
    return ret;
}
inline void write(int x) {
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}
int n,c,e,f,l,x,y,s,like,fear,dp[10009][40],num[10009][40],ans;
int main(){
    n=read();
    c=read();
    for(int i=1;i<=c;i++){
        e=read();
        f=read();
        l=read();
        like=0;
        fear=0;
        for(int j=0;j<f;j++){
            x=read();
            x=(x-e+n)%n;
            fear|=1<<x; 
        }
        for(int j=0;j<l;j++){
            y=read();
            y=(y-e+n)%n;
            like|=1<<y; 
        }
        for(int j=0;j<32;j++){
            if((j&fear)||(~j&like))
                num[e][j]++;
        }
    }
    for(int i=0;i<32;i++){
        memset(dp[0],0x80,sizeof(dp[0]));
        dp[0][i]=0;
        for(int j=1;j<=n;j++)
            for(int s=0;s<32;s++)
                dp[j][s]=max(dp[j-1][(s&15)<<1],dp[j-1][(s&15)<<1|1])+num[j][s];
        ans=max(ans,dp[n][i]); 
    }
    write(ans);
}