更好的阅读体验

原题

题目描述

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

输入格式

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

输出格式

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

数据范围

$1 \le n \le 10$,
$0 \le k \le n^2$

输入样例：

3 2

输出样例：

16

算法解析

算法构造

这道题目，根据数据范围，不难得出，这道题目考察的是状态压缩动态规划。

分析题目，我们可以得到如下信息。

1. 一个点的相邻八格，不可以有其他点。
2. 棋盘置点类型。

那么，我们接下来，思考两个流程。

1. 如何表示状态
2. 如何转移方程

表示状态

显然，题目给的条件，是国王总数是严格限制的，就是k个。

所以说，我们放置了多少个国王，是需要考虑的。

接着，根据棋盘类型的状态压缩动态规划的套路，每一行的状态，我们需要明白。

也就是每一行，哪些位置放了国王。

综上所述，我们可以得出，动态规划的状态表示。

$$ f[i][j][s]为所有只摆在前i行，目前摆了j个国王，而且第i行的摆放状态为s $$

我们可以举一个例子

$$ n=5 \\\\ f[1][2][20]表示第一行，已经摆了两个国王，摆在左边第一个，和左边第三个 \\\\ (20)_{10}=(10100)_{2} $$

状态转移

在这里，状态之间的转移，必然要满足，国王之间不会相互攻击到，那么我们进行分析。

两个国王，如果他们存在，直接靠近（上下左右）或者简介靠近（两斜对角），那么显然是不合法的。

因此，转换成为状态理解。

对于一个状态集合而言，显然不能存在相邻的1.
$$ 101 (可以) \quad 两个国王有间隔\\\\ 110 (不可以) \quad 国王1和国王2相邻，可以相互攻击\\\\ $$
因为这会导致，左右两个国王相邻，然后发起攻击。

而且，对于上下两行而言，不能有共同的一位有1

$$ 101 \\\\ 101 $$
因为这会导致，上下两个国王相邻，然后发起攻击。

我们讨论完了，上下左右，接下来是最难的两斜对角。
$$ 我们设，第i行的状态为a，第i+1行状态为b $$
那么
$$ S=a 或 b \\ 也就是S=a|b $$
是不可以存在，有相邻的1的。
$$ a=100 \\\\ b=010 \\\\ S=110 \\\\ $$
因此这会导致，两斜对角国王相互攻击。

综上所述，我们得到集合转移的约束条件。

下面是代码部分，有很详细的解说

解题代码

#include <bits/stdc++.h>
using namespace std;
const int N=(1<<10)+20;
vector<int> state,head[N];
//state放置合法状态,head[a]表示a对应的放置集合状态可以转移到的集合状态。
int n,k;
long long f[12][110][N];
int cnt[N];
inline bool check(int x)//这里是检查有没有出现相邻的两个1
{
    for(int i=0; i<n; i++)
        if ( (x>>i & 1) && (x>>i+1 & 1) )//第i位是1，而且第i+1位也是1
            return false;//左右攻击
    return true;
}
/*
这里是O(1)算法，来自抽风大佬！！！
inline bool check(int x)//这里是检查有没有出现相邻的两个1
{
    return !(x&x>>1);
}
*/
inline int count(int x)//统计这个状态有多少个1，也就是放置了多少个国王
{
    int ans=0;
    for(int i=0; i<n; i++)
        ans+=(x>>i & 1);
    return ans;
}
inline void pre()
{
    //首先我们找出，所有满足不可能左右攻击的合法放置国王的状态，这是第一步筛除不合法的方案
    for(int i=0; i<(1<<n); i++)
        if (check(i))//这里，我们存储所有无法左右攻击的合法状态
        {
            state.push_back(i);
            cnt[i]=count(i);//统计这个状态有多少个国王
        }
    for(int i=0; i<state.size(); i++)//枚举所有状态
        for (int j=0; j<state.size(); j++)
        {
            int a=state[i],b=state[j];
            if ( (a & b)==0 && check(a | b) )//这里第一个检查上下攻击，第二个检查两斜对角攻击
                head[i].push_back(j);//那么j对应状态，可以转移到i对应的状态。这里我们i,j都是状态对应的坐标
        }
}
inline void init()
{
    scanf("%d%d",&n,&k);
    pre();
    f[0][0][0]=1;
    for(int i=1; i<=n+1; i++)//n行转移，n+1行是为了好统计答案
        for(int j=0; j<=k; j++)//目前使用的国王棋子数量
            for(int a=0; a<state.size(); a++)
                for(int b=0; b<head[a].size(); b++)
                {
                    int c=cnt[state[a]];//统计state[a]对应的国王个数
                    if (j>=c)//目前一共放j个国王，从b转移到a，要满足国王数不超标
                        f[i][j][a]+=f[i-1][j-c][head[a][b]];
                }
    cout<<f[n+1][k][0]<<endl;//第n+1行什么都不放，相当于只在1~n行放国王，目前一共放了k个国王的总方案数，其实就是答案要求的方案
}
signed main()
{
    init();
    return 0;
}