提高级-动态规划-状压DP

# 状态压缩DP

---

## 一、定义

状态压缩动态规划，就是我们俗称的状压DP，是利用计算机二进制的性质来描述状态的一种DP方式。

很多棋盘问题都运用到了状压，同时，状压也经常和BFS及DP连用。

状压dp其实就是将状态压缩成2进制来保存 其特征就是看起来有点像搜索，每个格子的状态只有1或0 ，是另一类非常典型的动态规划。

---

举个例子：有一个大小为$n\times n$ 的农田，我们可以在任意处种田，现在来描述一下某一行的某种状态：

设$n = 9$；

有二进制数 100011011（九位），每一位表示该农田是否被占用，1表示用了，0表示没用，这样一种状态就被我们表示出来了：见下表

![](http://39.99.183.126:8888/file/2/dp-state1.png)

---

所以我们最多只需要 $2^{n + 1} - 1 $ 的十进制数就好（二进制形式是n个1） 现在我们有了表示状态的方法，但心里也会有些不安:上面用十进制表示二进制的数，枚举了全部的状态，DP起来复杂度岂不是很大？没错，状压其实是一种很暴力的算法，因为他需要遍历每个状态，所以将会出现 $2^n$ 的情况数量，不过这并不代表这种方法不适用：一些题目可以依照题意，排除不合法的方案，使一行的总方案数大大减少从而减少枚举

---

为了更好的理解状压dp，首先介绍位运算相关的知识。

1.  ’&’符号，x&y，会将两个十进制数在二进制下进行与运算(都1为1，其余为0） 然后返回其十进制下的值。例如3(11)&2(10)=2(10)。
2.  ’|’符号，x|y，会将两个十进制数在二进制下进行或运算（都0为0，其余为1） 然后返回其十进制下的值。例如3(11)|2(10)=3(11)。
3.  ’^’符号，x^y，会将两个十进制数在二进制下进行异或运算（不同为1，其余 为0）然后返回其十进制下的值。例如3(11)^2(10)=1(01)。
4. '\~' 符号，\~x，按位取反。例如 \~101=010 。
5. ’<<’符号，左移操作，x<<2，将x在二进制下的每一位向左移动两位，最右边用0填充，x<<2相当于让x乘以4。 ’>>’符号，是右移操作，x>>1相当于给x/2，去掉x二进制下的最右一位

---

1.判断一个数字x二进制下第i位是不是等于1。（最低第1位）

方法：`if(((1<<(i−1))&x)>0)` 将1左移i-1位，相当于制造了一个只有第i位 上是1，其他位上都是0的二进制数。然后与x做与运算，如果结果>0， 说明x第i位上是1，反之则是0。

2.将一个数字x二进制下第i位更改成1。

方法：`x=x|(1<<(i−1))` 证明方法与1类似。

3.将一个数字x二进制下第i位更改成0。

方法：`x=x&~(1<<(i−1))`

4.把一个数字二进制下最靠右的第一个1去掉。

方法：`x=x&(x−1)`

---

##  例题

[「SCOI2005」互不侵犯](http://39.99.183.126:8888/p/4154)

在 $N\times N$ 的棋盘里面放 $K$ 个国王（$1 \leq N \leq 9, 1 \leq K \leq N \times N$），使他们互不攻击，共有多少种摆放方案。
    
国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 $8$ 个格子。

---

### 解释

设 $f(i,j,l)$ 表示前 $i$ 行，第 $i$ 行的状态为 $j$，且棋盘上已经放置 $l$ 个国王时的合法方案数。

对于编号为 $j$ 的状态，我们用二进制整数 $sit(j)$ 表示国王的放置情况，$sit(j)$ 的某个二进制位为 $0$ 表示对应位置不放国王，为 $1$ 表示在对应位置上放置国王；用 $sta(j)$ 表示该状态的国王个数，即二进制数 $sit(j)$ 中 $1$ 的个数。例如，如下图所示的状态可用二进制数 $100101$ 来表示（棋盘左边对应二进制低位），则有 $sit(j)=100101_{(2)}=37, sta(j)=3$。

![](http://39.99.183.126:8888/file/2/SCOI2005-互不侵犯.png)

---

设当前行的状态为 $j$，上一行的状态为 $x$，可以得到下面的状态转移方程：$f(i,j,l) = \sum f(i-1,x,l-sta(j))$。

设上一行的状态编号为 $x$，在保证当前行和上一行不冲突的前提下，枚举所有可能的 $x$ 进行转移，转移方程：

$$
f(i,j,l) = \sum f(i-1,x,l-sta(j))
$$

---

### 实现

```cpp
#include <algorithm>
#include <iostream>
using namespace std;
long long sta[2005], sit[2005], f[15][2005][105];
int n, k, cnt;

void dfs(int x, int num, int cur) {
  if (cur >= n) {  // 有新的合法状态
    sit[++cnt] = x;
    sta[cnt] = num;
    return;
  }
  dfs(x, num, cur + 1);  // cur位置不放国王
  dfs(x + (1 << cur), num + 1,
      cur + 2);  // cur位置放国王，与它相邻的位置不能再放国王
}

bool compatible(int j, int x) {
  if (sit[j] & sit[x]) return false;
  if ((sit[j] << 1) & sit[x]) return false;
  if (sit[j] & (sit[x] << 1)) return false;
  return true;
}

int main() {
  cin >> n >> k;
  dfs(0, 0, 0);  // 先预处理一行的所有合法状态
  for (int j = 1; j <= cnt; j++) f[1][j][sta[j]] = 1;
  for (int i = 2; i <= n; i++)
    for (int j = 1; j <= cnt; j++)
      for (int x = 1; x <= cnt; x++) {
        if (!compatible(j, x)) continue;  // 排除不合法转移
        for (int l = sta[j]; l <= k; l++) f[i][j][l] += f[i - 1][x][l - sta[j]];
      }
  long long ans = 0;
  for (int i = 1; i <= cnt; i++) ans += f[n][i][k];  // 累加答案
  cout << ans << endl;
  return 0;
}
```

---

## 例题 2

[\[POI2004\] PRZ](http://www.luogu.com.cn/problem/P5911)

有 $n$ 个人需要过桥，第 $i$ 的人的重量为 $w_i$，过桥用时为 $t_i$. 这些人过桥时会分成若干组，只有在某一组的所有人全部过桥后，其余的组才能过桥。桥最大承重为 $W$，问这些人全部过桥的最短时间。
    
$100\le W \le 400$，$1\le n\le 16$，$1\le t_i\le 50$，$10\le w_i\le 100$.

---

### 解释

我们用 $S$ 表示所有人构成集合的一个子集，设 $t(S)$ 表示 $S$ 中人的最长过桥时间，$w(S)$ 表示 $S$ 中所有人的总重量，$f(S)$ 表示 $S$ 中所有人全部过桥的最短时间，则：

$$
\begin{cases}
    f(\varnothing)=0,\\
    f(S)=\min\limits_\{T\subseteq S;\~w(T)\leq W\}\left\\{t(T)+f(S\setminus T)\right\\}.
\end{cases}
$$

需要注意的是这里不能直接枚举集合再判断是否为子集，而应使用 子集枚举，从而使时间复杂度为 $O(3^n)$.

---

### 实现

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int W, n;
  cin >> W >> n;
  const int S = (1 << n) - 1;
  vector<int> ts(S + 1), ws(S + 1);
  for (int j = 0, t, w; j < n; ++j) {
    cin >> t >> w;
    for (int i = 0; i <= S; ++i)
      if (i & (1 << j)) {
        ts[i] = max(ts[i], t);
        ws[i] += w;
      }
  }
  vector<int> dp(S + 1, numeric_limits<int>::max() / 2);
  for (int i = 0; i <= S; ++i) {
    if (ws[i] <= W) dp[i] = ts[i];
    for (int j = i; j; j = i & (j - 1))
      if (ws[i ^ j] <= W) dp[i] = min(dp[i], dp[j] + ts[i ^ j]);
  }
  cout << dp[S] << '\n';
  return 0;
}
```

---

## 习题

-   [「NOI2001」炮兵阵地](http://39.99.183.126:8888/p/1907)
-   [「USACO06NOV」玉米田 Corn Fields](https://www.luogu.com.cn/problem/P1879)
-   [「九省联考 2018」一双木棋](http://39.99.183.126:8888/p/4155)