状压 DP

在程序中，我们如何保存一面棋盘？

$$ \def\arraystretch{2} \begin{array}{|c|c|c|c|}\hline \ & \Large♕ & \ & \Large♕ \\ \hline \Large♕ & \ & \Large♕ & \Large♕ \\ \hline \ & \ & \Large♕ & \ \\ \hline \Large♕ & \Large♕ & \ & \Large♕ \\ \hline \end{array} $$

用 $bool$ 数组 $A[ \ ][ \ ]$.$A[i][j]=1$ 表示第 $i$ 行第 $j$ 列有一枚棋子.

bool A[][] = {
    {0, 1, 0, 1},
    {1, 0, 1, 1},
    {0, 0, 1, 0},
    {1, 1, 0, 1}
};

现在我摆出了棋盘的第 $1$ 行和第 $4$ 行，并规定任意两个棋子不能相邻，则中间两行一共有多少种可行的摆法？

$$ \def\arraystretch{2} \begin{array}{|c|c|c|c|}\hline \Large♕ & \ & \Large♕ & \ \\ \hline \ & \ & \ & \ \\ \hline \ & \ & \ & \ \\ \hline \ & \Large♕ & \ & \Large♕ \\ \hline \end{array} $$

设 $f[\square\!\square\!\square\!\square][i]$ 表示从第 $1$ 行摆到第 $i$ 行，且第 $i$ 行摆放 $\square\!\square\!\square\!\square\!$ 的可行方案总数.

由于第一行只能为 $\blacksquare\!\square\!\blacksquare\!\square$，因此 $f[\blacksquare\!\square\!\blacksquare\!\square][1]=1$（$\square$ 表示这一格没有棋子，$\blacksquare$ 表示有棋子）.现在的目标是求 $f[\square\!\blacksquare\!\square\!\blacksquare][4]$.

因为黑棋和白棋不相邻，而第 $4$ 行已经给出，所以第 $3$ 行有 $4$ 种摆法（全空着也算一种摆法）：

于是可以列出递推方程：

$$ f[\square\!\blacksquare\!\square\!\blacksquare][4]=f[\blacksquare\!\square\!\blacksquare\!\square][3]+f[\blacksquare\!\square\!\square\!\square][3]+f[\square\!\square\!\blacksquare\!\square][3]+f[\square\!\square\!\square\!\square][3] $$

但这么做未免也太滑稽了，而且 $C++$ 并不支持特殊符号.那怎么办呢？

还记得我们如何 在程序中保存棋盘 吗？对，用 $bool$ 数组.例如 $\square\!\blacksquare\!\square\!\blacksquare$ 可以用 $bool$ 数组表示为 $\{0, 1, 0, 1\}$，然后再用 状态压缩 算法将它压缩成二进制数 $(0101)_2$.一顿操作之后，我们的方程就变为：

$$ f[(0101)_2][4]=f[(1010)_2][3]+f[(1000)_2][3]+f[(0010)_2][3]+f[(0000)_2][3] $$

看上去比之前像话多了.

将一组状态压缩成一个二进制数，塞进 $f[ \ ]$ 的中括号里，再进行递推，这就是「状压 $DP$」.

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

按照状压 $DP$ 的套路，这道题大抵需要我们用二进制数表示某一行的状态.

$$ \def\arraystretch{2} \begin{array}{|c|c|c|c|}\hline \color{white}{\Large ♕} & \Large♕ & \color{white}{\Large ♕} & \Large♕ \\ \hline \end{array} →\{0,1,0,1\}→(0101)_2 $$

为了后续的需要，我们需要进行预处理：

1. 筛选出所有符合题目条件的状态.

2. 保存每种合法状态对应的国王个数.

由于每行有 $n$ 个格子，因此表示状态的二进制数最大为 $2^n-1$.

int n, tot; // tot: 合法的状态个数
int state[]; // s[i]: 第 i 种合法的状态
int nums[]; // nums[i]: 第 i 种状态的国王数

void pre() {
    for(int i = 0; i < (1 << n); i ++) { // 枚举 i 为每一种状态
        if(i & (i << 1)) continue; // 如果不为 0，那么必定有两个国王是挨着的，不合法
        int cnt = 0; // 记录状态 i 中的国王数
        for(int j = i; j; j >>= 1)
            if(j & 1) cnt ++;
        state[++ tot] = i;
        nums[tot] = cnt;
    }
}

$f[i][s][k]$：棋盘的前 $i$ 行已经摆好，第 $i$ 行摆的状态是 $s$，并且一共摆了 $k$ 个国王时有几种合法的方案.

int f[][][], ans;

bool avl(int a, int b) { // 若上一行的状态是 a，判断下一行的状态能否是 b
	return (!(a & b)) && (!((a << 1) & b)) && (!((a >> 1) & b));
}

void dp() {
    f[0][1][0] = 1;
    for(int i = 1; i <= n; i ++) // 放前 i 行 
        for(int s = 1; s <= tot; s ++) // 第 i 行的状态是 s
            for(int k = nums[s]; k <= m; k ++) // 一共摆了 k 个国王 
                for(int t = 1; t <= tot; t ++) // 第 i - 1 行的状态是 t
                    if(avl(state[s], state[t]))
                        f[i][s][k] += f[i - 1][t][k - nums[s]];
    for(int i = 1; i <= tot; i ++)
        ans += f[n][i][m];
    cout << ans;
}