题目描述

在 $n×n$ 的棋盘上放 $k$ 个国王，国王可攻击相邻的 $8$ 个格子，求使它们无法互相攻击的方案总数。

输入格式

共一行，包含两个整数 $n$ 和 $k$。

输出格式

共一行，表示方案总数，若不能够放置则输出$0$。

数据范围

$1≤n≤10$,
$0≤k≤n^2$

输入样例

3 2

输出样例

16

状压dp

状态表示：①集合：$f[i][j][k]$ 前$i$行对应第$i$行的状态是$j$且一共有$k$个骑士情况。 ②属性：数目
状态计算：$f[i][j][k] += f[i - 1][t][k - num[j]]$
第$i$行的状态是$j$，第$i-1$行的状态是$t$。如果两状态不冲突即可以转移

限制条件

①在同一行不能有相邻的骑士 同行约束即 (j&j<<1)==0
②该行与上一行的互相约束 !st[t][j]或者st[t][j]==0

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=11,M=1<<N;
int n,m;
bool st[M][M];//对于i-1行和i行状态是否满足条件的状态数组 1表示不满足条件 0表示满足
int num[M];//记录现在的状态有几个骑士 二进制中1的个数 预处理
ll f[N][M][N*N];
int main()
{
    cin>>n>>m;  //放置m个骑士
    //如果该行状态是j  前一行的状态是i  判断此状态会不会出现矛盾
    for(int i=0;i<1<<n;i++)
        for(int j=0;j<1<<n;j++)
            for(int k=0;k<n;k++)
                if((i>>k&1)&&(j>>k&1||(k&&(j>>(k-1)&1))||(k<n-1&&j>>k+1&1)))//如果该行与前一行有相同位置的1或者错一位的1直接标记
                {
                        st[i][j]=1;
                        break;
                }
    for(int i=0;i<1<<n;i++)
    {
        int t=i;
        while(t)
        {
            t-=t&-t;
            num[i]++;
        }
    }
    f[0][0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<1<<n;j++)//第i行的状态
            if((j & (j << 1)) == 0)//同一行的限制条件 同一行相邻不能有骑士  不能有连续的1
                for(int k=0;k<=m;k++)//放置了几个骑士    
                    for(int t=0;t<1<<n;t++)//枚举第i-1行的状态
                        if(((t&(t<<1))==0)&&(num[j]<=k)&&(!st[t][j])) 
                            f[i][j][k]+=f[i-1][t][k-num[j]];


    ll res=0;
    for(int i=0;i<1<<n;i++)    res+=f[n][i][m];

    cout<<res<<endl;
    return 0;

}