【[APIO2007]动物园】

我好\(sb\)啊，把\(>>\)打成\(<<\)结果就写了两节课

那个一个人只能看到五个动物显然很鬼畜

那我们就可以压这一维了

\(dp[i][s]\)表示从第\(i\)个位置往后数五个位置的状态是\(s\)时最多能有几个小朋友开心(\(0\)表示移走，\(1\)表示保留)

之后我们处理处每一个人的喜欢和害怕的状态，往下转移就好了

还有这是一个环，感觉非常不好处理的样子

我们可以枚举第一个位置之后的状态是什么，最后的位置必须和第一个位置吻合就好了

复杂度\(O(4^5n)\)

代码

#include<iostream>

#include<cstring>

#include<cstdio>

#define re register

#define max(a,b) ((a)>(b)?(a):(b))

#define maxn 50005

int dp[10005][33];

int S[maxn],F[maxn],L[maxn];

int ans=0;

inline int read()

{

    char c=getchar();

    int x=0;

    while(c<'0'||c>'9') c=getchar();

    while(c>='0'&&c<='9')

        x=(x<<3)+(x<<1)+c-48,c=getchar();

    return x;

}

int n,m,now;

int main()

{

    n=read(),m=read();

    int t1,t2;

    for(re int i=1;i<=m;i++)

    {

        S[i]=read();

        t1=read(),t2=read();

        int x;

        F[i]=31;

        for(re int j=1;j<=t1;j++)

        {

            x=read()-S[i];

            if(x<0) x+=n;

            F[i]^=(1<<x);

        }

        for(re int j=1;j<=t2;j++)

        {

            x=read()-S[i];

            if(x<0) x+=n;

            L[i]|=(1<<x);

        }

    }

    for(re int s=0;s<=31;s++)

    {

        memset(dp,-20,sizeof(dp));

        now=1;

        for(re int i=0;i<=31;i++) dp[1][i]=-21232;

        dp[1][s]=0;

        while(S[now]==1)

        {

            if((L[now]&s)||((F[now]|s)!=31)) dp[1][s]++;

            now++;

        }

        for(re int i=1;i<n;i++)

        {

            for(re int j=0;j<=31;j++)

            {

                dp[i+1][(j>>1)|(1<<4)]=max(dp[i][j],dp[i+1][(j>>1)|(1<<4)]);

                dp[i+1][j>>1]=max(dp[i][j],dp[i+1][j>>1]);

            }

            while(S[now]==i+1)

            {

                for(re int j=0;j<=31;j++)

                    if((L[now]&j)||((F[now]|j)!=31)) dp[i+1][j]++;

                now++;

            }

        }

        int t=s;

        t^=(1<<4);

        if(t>s) t-=(1<<4);

        for(re int i=0;i<=31;i++)

            if((i>>1)==t) ans=max(ans,dp[n][i]);

    }

    std::cout<<ans;

    return 0;

}