简介

我们从一个案例入手状压 DP。

EXAMPLE

假设我们有一张棋盘：

$$\begin{array}{|cccc|}\hline ♘& ♘& ♘& ♘\\ ♘& ♘& ♘& ♘\\ ♘& ♘& ♘& ♘\\ ♘& ♘& ♘& ♘\\ \hline\end{array}$$

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

$$\begin{array}{|cccc|}\hline ♘& ♘& ♘& ♘\\ ♘& ♘& ♘& ♘\\ ♘& ♘& ♘& ♘\\ ♘& ♘& ♘& ♘\\ \hline\end{array}$$

设 $f[\ast ,i]$ 表示从第 $1$ 行摆到第 $i$ 行，并且第 $i$ 行摆放状态为 $\ast$ 的可行方案总数。

由于第一行是题目给定的，因此我们有边界条件：

$$f[\begin{array}{|cccc|}\hline ♘& ♘& ♘& ♘\\ \hline\end{array},1]=1$$

目标是求出

$$f[\begin{array}{|cccc|}\hline ♘& ♘& ♘& ♘\\ \hline\end{array},4]$$

题目要求棋子不相邻，而第 $4$ 行也已给出，所以第 $3$ 行有 $4$ 种摆法：

$$\begin{array}{r}1.\begin{array}{|cccc|}\hline ♘& ♘& ♘& ♘\\ \hline\end{array}\\ 2.\begin{array}{|cccc|}\hline ♘& ♘& ♘& ♘\\ \hline\end{array}\\ 3.\begin{array}{|cccc|}\hline ♘& ♘& ♘& ♘\\ \hline\end{array}\\ 4.\begin{array}{|cccc|}\hline ♘& ♘& ♘& ♘\\ \hline\end{array}\end{array}$$

于是列出状态转移方程：

$$\begin{array}{r}\mathit{\text{f}}[\begin{array}{|cccc|}\hline ♘& ♘& ♘& ♘\\ \hline\end{array},4]=\mathit{\text{f}}[\begin{array}{|cccc|}\hline ♘& ♘& ♘& ♘\\ \hline\end{array},3]+\mathit{\text{f}}[\begin{array}{|cccc|}\hline ♘& ♘& ♘& ♘\\ \hline\end{array},3]\\ +\mathit{\text{f}}[\begin{array}{|cccc|}\hline ♘& ♘& ♘& ♘\\ \hline\end{array},3]+\mathit{\text{f}}[\begin{array}{|cccc|}\hline ♘& ♘& ♘& ♘\\ \hline\end{array},3]\end{array}$$

看起来很差，而且 C++ 并不支持这种形式。怎么办呢？

采用 状态压缩 算法。可以用 $1$ 表示有棋子，$0$ 表示没棋子，进而用一个二进制数表示每一行的摆放：

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

采用 状态压缩 表示状态的动态规划，就是状压 DP。

例

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

预处理

每一行的状态都用一个二进制数表示：

$$\begin{array}{|cccc|}\hline ♘& ♘& ♘& ♘\\ \hline\end{array}\to \{0,1,0,1\}\to (0101{)}_2$$

需要进行预处理：

1. 筛选出所有符合题目条件的状态；
2. 计算并保存每种合法状态对应的国王个数。

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

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

void pre() {
    // 枚举 i 为每一种状态
    for (int i = 0; i < (1 << n); i ++) {
        // 如果不为 0，则存在相邻的国王，不合法
        if (i & (i << 1))
            continue;
        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]$：满足以下条件时，有几种合法的方案：

1. 棋盘的前 $i$ 行已经摆好；
2. 第 $i$ 行的状态是 $\mathrm{state}[s]$；
3. 一共摆了 $k$ 个国王。

$\mathrm{avl}(a,b)$：若当前行的状态是 $a$，判断上一行的状态能否是 $b$。

$$f[i,s,k]=\sum _{\mathrm{avl}(\mathrm{state}[s],\mathrm{state}[t])}f[i-1,t,k-\mathrm{nums}[s]]$$

问题的解是

$$\sum _{i}f[n,i,m]$$

int f[][][], ans;

// 若当前行的状态是 a，判断上一行的状态能否是 b
bool avl(int a, int 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;
}