BZOJ1087 [SCOI2005]互不侵犯King 状态压缩动态规划

时间：2023-03-09 15:04:48
BZOJ1087 [SCOI2005]互不侵犯King 状态压缩动态规划

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解

题目传送门 - BZOJ1087

题意概括

　　在n*n的棋盘上面放k个国王，使得他们互相无法攻击，问有多少种摆法。

题解

　　dp[i][j][x]表示前i行，状态为j，总共放了x个国王的方案总数。

　　然后简单的转移一下即可。

　　当然这样要炸。

　　只需要在这之前把每行的合法情况筛选一下即可，这样的情况总数不到100。

　　然后就可以了。

代码

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#include <cmath>

using namespace std;

typedef long long LL;

const int S=(<<)+;

int n,k;

int sit[S],bitsum[S],sz;

LL dp[][S][];

int cnt1(int x){

    int ans=;

    while (x){

        ans+=x&;

        x>>=;

    }

    return ans;

}

int main(){

    scanf("%d%d",&n,&k);

    sz=;

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

        if (!(i&(i<<)))

            sit[++sz]=i,bitsum[sz]=cnt1(i);

    memset(dp,,sizeof dp);

    dp[][][]=;

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

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

            for (int x=;x<=k;x++){

                if (!dp[i][j][x])

                    continue;

                for (int y=;y<=sz;y++)

                    if (!(sit[j]&sit[y])&&!(sit[j]&(sit[y]<<))&&!((sit[j]<<)&sit[y])&&x+bitsum[y]<=k)

                        dp[i+][y][x+bitsum[y]]+=dp[i][j][x];

            }

    LL ans=;

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

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

    printf("%lld",ans);

    return ;

}