题意

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。

\(N \leq 9,K \leq N \times N\)

分析

又是一道看题意和数据范围就能猜出状态\(f(i,k,s)\)的题。

表示前\(i\)行放\(k\)个国王，第\(i\)行的状态为\(s\)的方案数。

然后是一些小技巧，能攻击到就是左右移或不移，并起来为0。可以预处理合法状态，状态中的1的个数，合法可转移的状态。

时间复杂度\(O(N K 2^{2N})\)

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<ctime>
#include<cstring>
#define rg register
#define il inline
#define co const
template<class T>il T read()
{
    rg T data=0;
    rg int w=1;
    rg char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            w=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        data=data*10+ch-'0';
        ch=getchar();
    }
    return data*w;
}
template<class T>T read(T&x)
{
    return x=read<T>();
}
using namespace std;
typedef long long ll;

co int N=9;
int n,m;
int cnt[1<<N],c1[1<<N],c2[1<<N][1<<N];
ll f[N+1][N*N+1][1<<N];

void init()
{
    for(int i=0;i<(1<<n);++i)
        if((i & (i >> 1)) == 0)
        {
            int s=0;
            for(int x=i;x;x>>=1)
                s+=(x&1);
            cnt[i]=s;
            c1[i]=1;
        }
    for(int i=0;i<(1<<n);++i)
        if(c1[i])
            for(int j=0;j<(1<<n);++j)
                if(c1[j])
    if((i & j) == 0 && (i & (j >> 1)) == 0 && (j & (i >> 1)) == 0)
        c2[i][j]=1;
}

void solve()
{
    for(int i=0;i<(1<<n);++i)
        if(c1[i])
            f[1][cnt[i]][i]=1;
    for(int j=1;j<n;++j)
        for(int k=0;k<(1<<n);++k)
            if(c1[k])
                for(int i=0;i<(1<<n);++i)
                    if(c1[i])
    if(c2[k][i])
        for(int p=cnt[k];p+cnt[i]<=m;++p)
            f[j+1][p+cnt[i]][i]+=f[j][p][k];
}

int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    read(n);read(m);
    init();
    solve();
    ll ans=0;
    for(int i=0;i<(1<<n);++i)
        ans+=f[n][m][i];
    printf("%lld\n",ans);
    return 0;
}

BZOJ1087 [SCOI2005]互不侵犯King

原文：https://www.cnblogs.com/autoint/p/10062500.html