跳转至

# 状压 DP

## 简介

状压 DP 是动态规划的一种，通过将状态集合转化为整数记录在 DP 状态中来实现状态转移的目的．

为了达到更低的时间复杂度，通常需要寻找更低状态数的状态．大部分题目中会利用二元状态，用 𝑛 n 位二进制数表示 𝑛 n 个独立二元状态的情况．

使用状态压缩通常涉及位操作，关于基础位操作详见 位操作 页面．

## 例题 1

「SCOI2005」互不侵犯

在 𝑁 ×𝑁 N×N 的棋盘里面放 𝐾 K 个国王（1 ≤𝑁 ≤9,1 ≤𝐾 ≤𝑁 ×𝑁 1≤N≤9,1≤K≤N×N），使他们互不攻击，共有多少种摆放方案．

国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 8 8 个格子．

### 解释

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

对于编号为 𝑗 j 的状态，我们用二进制整数 𝑠 𝑖 𝑡(𝑗)s i t(j) 表示国王的放置情况，𝑠 𝑖 𝑡(𝑗)s i t(j) 的某个二进制位为 0 0 表示对应位置不放国王，为 1 1 表示在对应位置上放置国王；用 𝑠 𝑡 𝑎(𝑗)s t a(j) 表示该状态的国王个数，即二进制数 𝑠 𝑖 𝑡(𝑗)s i t(j) 中 1 1 的个数．例如，如下图所示的状态可用二进制数 1 0 0 1 0 1 100101 来表示（棋盘左边对应二进制低位），则有 𝑠 𝑖 𝑡(𝑗) =1 0 0 1 0 1(2) =3 7,𝑠 𝑡 𝑎(𝑗) =3 s i t(j)=100101(2)=37,s t a(j)=3．

设当前行的状态为 𝑗 j，上一行的状态为 𝑥 x，可以得到下面的状态转移方程：𝑓(𝑖,𝑗,𝑙) =∑𝑓(𝑖 −1,𝑥,𝑙 −𝑠 𝑡 𝑎(𝑗))f(i,j,l)=∑f(i−1,x,l−s t a(j))．

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

𝑓(𝑖,𝑗,𝑙)=∑𝑓(𝑖−1,𝑥,𝑙−𝑠 𝑡 𝑎(𝑗))f(i,j,l)=∑f(i−1,x,l−s t a(j))

### 实现

参考代码

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    #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

有 𝑛 n 个人需要过桥，第 𝑖 i 的人的重量为 𝑤 𝑖 w i，过桥用时为 𝑡 𝑖 t i. 这些人过桥时会分成若干组，只有在某一组的所有人全部过桥后，其余的组才能过桥．桥最大承重为 𝑊 W，问这些人全部过桥的最短时间．

1 0 0 ≤𝑊 ≤4 0 0 100≤W≤400，1 ≤𝑛 ≤1 6 1≤n≤16，1 ≤𝑡 𝑖 ≤5 0 1≤t i≤50，1 0 ≤𝑤 𝑖 ≤1 0 0 10≤w i≤100.

### 解释

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

{𝑓(∅)=0,𝑓(𝑆)=m i n 𝑇⊆𝑆; 𝑤(𝑇)≤𝑊{𝑡(𝑇)+𝑓(𝑆∖𝑇)}.{f(∅)=0,f(S)=min T⊆S; w(T)≤W{t(T)+f(S∖T)}.

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

### 实现

参考代码

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    #include <iostream>
    #include <limits>
    #include <vector>
    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」炮兵阵地
- 「USACO06NOV」玉米田 Corn Fields
- 「九省联考 2018」一双木棋

> 本页面最近更新：2026/1/27 12:26:08，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：StudyingFather, Ir1d, H-J-Granger, NachtgeistW, countercurrent-time, Enter-tainer, ouuan, Marcythm, sshwy, Tiphereth-A, AngelKitty, c-forrest, CCXXXI, cjsoft, diauweb, Early0v0, ezoixx130, GekkaSaori, Henry-ZHR, HeRaNO, Konano, LovelyBuggies, Makkiy, mgt, minghu6, P-Y-Y, PotassiumWings, SamZhangQingChuan, Suyun514, weiyong1024, chieh2lu2, Chrogeek, GavinZhengOI, Gesrua, hhc0001, hsfzLZH1, iamtwz, kenlig, ksyx, kxccc, Link-cute, lychees, Peanut-Tang, REYwmp, shinzanmono, SukkaW, TianKong-y, TOMWT-qwq, Xeonacid, YuJunDongGit, zhb2000
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用