$\LARGE\color{orange}{刷题日记(算法提高课)}$

这种棋盘类的 DP 问题首先考虑状态压缩 DP

我们定义 $f[i][j][k]$ 表示集合为：考虑前 $i$ 行，目前已放置了 $j$ 个国王，其第 $i$ 行的状态为 $k$ 的所有可能，属性为方案数

这里的 $k$ 是一个二进制表示的数

由于第 $i$ 行的状态仅受前一行影响，因此我们需要考虑的是，在第 $i$ 行状态确定的时候，第 $i-1$ 行的状态如何取才合法，也就是我们只需要考虑两行即可

对于任意两个状态 $a,\ b$，需要满足如下条件：

• 不能有两个相邻的 1

• $a\& b==0$ ，即不能有两个国王处于同一列当中

• $a\| b$ 需要满足第一点，因为任意两个国王在纵向上不能相邻

我们首先预处理出来所有合法的状态，放在 $states$ 中

其次，我们预处理出来状态 $a$ 与状态 $b$ 不产生冲突（满足上述三点要求）的所有情况，放在 $heads$ 中

状态转移方程很简单，我们枚举第 $i$ 层所有合法的状态 $a$，如果某个状态 $b$ 不与 $a$ 产生冲突，则表示可以从 $b$ 转移过来

为了方便，我们还需要额外一个数组 $cnt$ 来存储当前状态中有多少个 1

综上，状态转移方程为：

$$ f[i][j][a]+=f[i-1][j-cnt[b]][b],\ 其中 a,\ b 表示状态 $$

最后我结果我们之间输出 $f[n + 1][k][0]$ ，表示考虑到第 $n+1$ 行，已经放了 $k$ 个国王，且第 $n+1$ 行的状态为 0 ，即表示一个国王都不放

完整代码：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 12, M = 1 << 10, K = 110;

long long f[N][K][M];

int cnt[M];
vector<int> states;
vector<int> heads[M];
int n, k;

bool check(int status)
{
    for(int i = 0; i < n; i++)
        if(status >> i & 1 && status >> i + 1 & 1)
            return false;
    return true;
}

int count(int status)
{
    int ans = 0;
    for(int i = 0; i < n; i++)
        ans += status >> i & 1;
    return ans;
}

int main()
{
    cin >> n >> k;

    for(int i = 0; i < 1 << n; i++)
        if(check(i))
        {
            states.push_back(i);
            cnt[i] = count(i);
        }

    for(int i = 0; i < states.size(); i++)
        for(int j = 0; j < states.size(); j++)
        {
            int a = states[i], b = states[j];
            if((a & b) == 0 && check(a | b))
                heads[i].push_back(j);
        }
    f[0][0][0] = 1;
    for(int i = 1; i <= n + 1; i++)
        for(int j = 0; j <= k; j++)//棋盘当中一个都不放也需要遍历
            for(int a = 0; a < states.size(); a++)//这里的a,b均不是状态
                for(int b : heads[a])
                    if(j >= cnt[states[b]])
                        f[i][j][a] += f[i - 1][j - cnt[states[b]]][b];
    cout << f[n + 1][k][0] << endl;
    return 0;
}