<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

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

输入格式

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

输出格式

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

数据范围

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

输入样例：

3 2

输出样例：

16

思路

闫氏$DP$分析法：

状态表示：$f_{i,j,s}$

• 集合：当前摆到了第$i$层，用了$j$个国王，并且当前行的状态是$s$（如果$s>>i\&1$那么第$i$个格子有国王，反之没有）
• 属性：$\text{count}$

状态计算：

• 如果上一行状态是$a$且是合法状态，那么数量就是$f_{i - 1,j - count_a,a}$。
• 所以状态转移方程就是$f_{i,j,s} += f_{i - 1,j - count_a,a}$

这里我们的代码为了不超时，换了新的写法，具体见代码注释。

代码

#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 12,M = 1 << N;
int n,m;
int cnt[M];
LL f[N][N * N][M];
vector <int> state;
vector <int> h[M];
bool check (int x) {    //判断有没有相邻的1
    for (int i = 0;i < n - 1;i++) {
        if ((x >> i & 1) && (x >> i + 1 & 1)) return false;
    }
    return true;
}
int count (int x) { //数出1的个数
    int ans = 0;
    for (int i = 0;i < n;i++) ans += x >> i & 1;
    return ans;
}
int main () {
    cin >> n >> m;
    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)) h[i].push_back (j); 
            //算出每一个状态能转移状态有哪些，这里存的是在state中的下标
        }
    }
    f[0][0][0] = 1;
    for (int i = 1;i <= n + 1;i++) {
        for (int j = 0;j <= m;j++) {
            for (int a = 0;a < state.size ();a++) {
                for (int b : h[a]) {
                    int c = cnt[state[a]];
                    if (j >= c) f[i][j][a] += f[i - 1][j - c][b];   //状态转移
                }
            }
        }
    }
    cout << f[n + 1][m][0] << endl;//因为所有的状态都可以转移到0，所以不用算答案，
    // 直接输出f[n + 1][m][0]，这里0本来就是state里的第一个数，所以不影响
    return 0;
}