【Luogu】P1896互不侵犯King（状压DP）

　　题目链接

　　真是可恶，被数据范围坑了一把。想要一遍AC的希望破灭了……

　　以后大家在做状压DP的时候一定要开long long……

　　设f[i][j][k]表示考虑前i行，总共放了j个King，第i行状态为k时的方案数。

　　先统计出k的二进制位有多少1，记为len，然后枚举o（1~(1<<n)-1），则状态转移方程有：

　　f[i][j][l]+=f[i-1][j-len][o];

　　注意判断两个状态是否合法。

　　j&(j>>1)不行，o&j不行，(o>>1)&j不行，(o<<1)&j也不行。当然o&(o>>1)更不行。

　　最后累计答案。

　　代码如下

#include<cstdio>

#include<cctype>

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

long long f[][][];

inline int getlen(long long x){

    int ans=;

    bool s;

    while(x){

        if(x&)    ans++;

        x>>=;

    }

    return ans;

}

long long Max;

long long ans;

inline bool check(long long x,long long y){

    if(x&y)    return ;

    if((x>>)&y)    return ;

    if((x<<)&y)    return ;

    return ;

}

int main(){

    f[][][]=;

    int n=read(),k=read();

    Max=(<<n)-;

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

        for(int j=;j<=k;++j)

            for(int l=;l<=Max;++l){

                int len=getlen(l);

                if(len>j)        continue;

                if(l&(l>>))    continue;

                for(int o=;o<=Max;++o){

                    if(check(o,l))    continue;

                    if(o&(o>>))    continue;

                    f[i][j][l]+=f[i-][j-len][o];

                }

            }

    for(int i=;i<=Max;++i)

        ans+=f[n][k][i];

    printf("%lld",ans);

    return ;

}

巴特西

【Luogu】P1896互不侵犯King（状压DP）

最新文章

热门文章