InoueMoby's Blog

前言

前面几篇的 DP，状态都是一个整数（容量 $j$ 、位置 $i$ ）或两个整数（位置 $(i,j)$ ）。但有一类问题，状态是一个集合——“已经选了哪些元素”。暴力枚举所有子集是 $2^N$ 种， $N=20$ 就有 100 万。怎么存一个集合？用一个整数的二进制位——第 $i$ 位是 1 表示元素 $i$ 已选，0 表示未选。这就是状态压缩（bitmask DP）。

最经典的应用是旅行商问题（TSP）：访问所有城市恰好一次再回到起点，最短路程是多少？暴力枚举排列 $O(N!)$ ， $N=15$ 就是 $10^{12}$ 。用 bitmask DP 压到 $O(2^N \cdot N^2)$ ， $N=15$ 只有 $7 \times 10^6$ ——从不可能变成 1 秒跑完。

问题的本质

从排列到子集

TSP 暴力为什么是 $N!$ ？因为你在枚举访问顺序。但实际上，很多顺序共享同样的”已访问集合”——比如先去 A 再去 B 再去 C，和先去 C 再去 B 再去 A，如果当前在 B 且已访问 {A,C}，后续的最优路径完全一样。这就是 DP 能省掉重复计算的关键。

用一个 $N$ 位二进制数表示”已访问的集合”：mask = 0b1011 表示城市 0、1、3 已访问，城市 2 未访问。检查城市 $i$ 是否已访问：mask >> i & 1。把城市 $i$ 标记为已访问：mask | (1 << i)。

bitmask 操作速查

操作	C++	含义
检查第 $i$ 位	`mask >> i & 1`	城市 $i$ 是否已访问
设置第 $i$ 位	`mask \|(1 << i)`	标记城市 $i$ 已访问
清除第 $i$ 位	`mask & ~(1 << i)`	取消访问
枚举子集	`for (int s = mask; s; s = (s-1) & mask)`	遍历所有非空子集
集合大小	`__builtin_popcount(mask)`	已访问几个城市

状态设计

$dp[mask][i]$ = 已访问集合为 $mask$ 、当前在城市 $i$ 的最短路径长度。

转移：从城市 $j$ 走到城市 $i$ ，mask 的第 $i$ 位从 0 变 1：

$dp[mask | (1<<i)][i] = \min_j(dp[mask][j] + dist[j][i])$

其中 $j$ 是 mask 中已访问的城市。

初始值： $dp[0][0] = 0$ （从城市 0 出发，还没访问任何城市——城市 0 会在最后回程时被算入）。

答案： $dp[(1<<N)-1][0]$ （所有城市都访问完，回到城市 0）。

理论 + 代码

TSP 完整实现

教材 4.8 节 B23 的核心代码：

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

double dp[1 << 16][16];
double dist[16][16];
int X[16], Y[16];

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) scanf("%d%d", &X[i], &Y[i]);

    // ① 预计算距离矩阵
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            dist[i][j] = sqrt(1.0*(X[i]-X[j])*(X[i]-X[j]) + 1.0*(Y[i]-Y[j])*(Y[i]-Y[j]));

    // ② 初始化
    for (int i = 0; i < (1 << N); i++)
        for (int j = 0; j < N; j++)
            dp[i][j] = 1e18;
    dp[0][0] = 0;                            // 从城市 0 出发

    // ③ 枚举所有状态
    for (int mask = 0; mask < (1 << N); mask++)
        for (int j = 0; j < N; j++) {
            if (dp[mask][j] >= 1e18) continue; // ④ 不可达状态跳过
            // ⑤ 从 j 出发，尝试访问未访问的城市 k
            for (int k = 0; k < N; k++) {
                if ((mask >> k) & 1) continue;  // ⑥ k 已访问，跳过
                int nmask = mask | (1 << k);
                dp[nmask][k] = min(dp[nmask][k], dp[mask][j] + dist[j][k]);
            }
        }
    printf("%.12lf\n", dp[(1<<N)-1][0]);      // ⑦ 回到城市 0
}

逐行解析：

① 预计算所有城市对之间的距离，避免重复计算 sqrt。
②③ dp 数组大小 $(2^N) \times N$ 。 $N=15$ 时约 $32K \times 15 \approx 500K$ 个状态。
④ 如果当前状态不可达（距离仍是 INF），跳过。
⑤⑥ 枚举所有未访问的城市 $k$ ，尝试从 $j$ 走到 $k$ 。(mask >> k) & 1 检查 $k$ 是否已访问。
⑦ dp[(1<<N)-1][0]：所有位都是 1（全部访问）且回到城市 0。

模拟： $N=3$ ，城市坐标 $(0,0), (0,1), (1,0)$ 。距离： $d_{01}=1, d_{02}=1, d_{12}=\sqrt{2}$ 。

mask	j	可转移的 k	dp 更新
000	0	1,2	dp[001][1]=1, dp[010][2]=1
001	1	2	dp[011][2]=1+√2≈2.414
010	2	1	dp[011][1]=1+√2≈2.414
011	1	— (全部访问)	dp[111][0]=2.414+1=3.414
011	2	—	dp[111][0]=2.414+1=3.414

最终 dp[111][0] = 3.414 ≈ $2 + \sqrt{2}$ 。路径 0→1→2→0 或 0→2→1→0。✓

例题

例题 1：TB B23 — Traveling Salesman Problem

题目： $N$ 个城市，坐标 $(X_i, Y_i)$ 。从城市 1 出发访问所有城市恰好一次再回到城市 1，求最短路程。

数据范围： $2 \le N \le 15$

—— AtCoder Tessoku Book B23

分析：教材 4.8 节原题。标准 bitmask DP， $O(2^N \cdot N^2)$ 。

输入样例：

输出：4.000000000000

代码：

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

double dp[1 << 16][16];

int main() {
    int N;
    scanf("%d", &N);
    int X[16], Y[16];
    for (int i = 0; i < N; i++) scanf("%d%d", &X[i], &Y[i]);

    for (int i = 0; i < (1 << N); i++)
        for (int j = 0; j < N; j++) dp[i][j] = 1e18;
    dp[0][0] = 0;                                    // ① 从城市 0 出发

    for (int mask = 0; mask < (1 << N); mask++)
        for (int j = 0; j < N; j++) {
            if (dp[mask][j] >= 1e18) continue;
            for (int k = 0; k < N; k++) {
                if ((mask >> k) & 1) continue;        // ② k 已访问
                double d = sqrt(1.0*(X[j]-X[k])*(X[j]-X[k]) + 1.0*(Y[j]-Y[k])*(Y[j]-Y[k]));
                int nmask = mask | (1 << k);
                dp[nmask][k] = min(dp[nmask][k], dp[mask][j] + d); // ③ 转移
            }
        }
    printf("%.12lf\n", dp[(1<<N)-1][0]);              // ④ 回到起点
}

逐行解析：

① 从城市 0（编号 1）出发，初始状态 mask=0，距离 0。
② (mask >> k) & 1：检查城市 $k$ 是否已在访问集合中。
③ 从城市 $j$ 走到城市 $k$ ，新的访问集合 nmask = mask | (1<<k)。
④ 所有城市都访问完（mask 所有位都是 1），回到城市 0 的距离就是答案。

验证： $N=4$ ，坐标 $(0,0), (0,1), (1,0), (1,1)$ 。路径 $0→1→3→2→0$ ： $1+1+1+1=4$ 。✓

例题 2：T90 045 — Simple Grouping（★6， bitmask 分组）

题目： $N$ 个点分成 $K$ 组（每组至少一个点），最小化”所有组中最大组内距离”的平方。组内距离 = 该组内任意两点距离的最大值。

数据范围： $2 \le K < N \le 15$

—— AtCoder Typical 90 045

分析： $N \le 15$ ，可以枚举所有分组方案。但直接枚举 $K^N$ 种分配太多了。

换个思路：预计算每个子集的组内最大距离，然后用 bitmask DP 枚举如何把全集划分成 $K$ 个不相交子集。

对于子集 $S$ ，diam[S] = $S$ 中所有点对距离的最大值。预计算 $O(2^N \cdot N^2)$ 。

然后 $dp[mask]$ = 把集合 $mask$ 划分成若干组时，最大组内距离的最小值。枚举 $mask$ 的子集 $sub$ 作为一组， $dp[mask] = \min_{sub}(\max(dp[mask \setminus sub],\ diam[sub]))$ 。但还需要控制恰好 $K$ 组。

更简单的方法：直接枚举所有大小为 $K$ 的划分。因为 $N \le 15$ ，枚举所有可能的分组方案可以用”枚举子集”技巧。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

long long diam[1 << 15]; // diam[S] = 子集 S 内的最大距离平方
long long dp[1 << 15];   // dp[mask] = 划分 mask 的最大组内距离的最小值
int X[16], Y[16];

int main() {
    int N, K;
    scanf("%d%d", &N, &K);
    for (int i = 0; i < N; i++) scanf("%d%d", &X[i], &Y[i]);

    // ① 预计算每个子集的组内最大距离（平方）
    for (int mask = 0; mask < (1 << N); mask++) {
        diam[mask] = 0;
        for (int i = 0; i < N; i++)
            for (int j = i + 1; j < N; j++)
                if ((mask >> i & 1) && (mask >> j & 1)) {
                    long long d = 1LL*(X[i]-X[j])*(X[i]-X[j]) + 1LL*(Y[i]-Y[j])*(Y[i]-Y[j]);
                    diam[mask] = max(diam[mask], d);
                }
    }

    // ② DP：dp[mask] = 划分 mask 为若干组，最大组内距离的最小值
    for (int mask = 0; mask < (1 << N); mask++) {
        dp[mask] = diam[mask]; // ③ 不分割，整组作为一个
        // ④ 枚举 mask 的所有非空真子集 sub
        for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
            if (sub == mask) continue; // 跳过自身
            int rest = mask ^ sub;
            dp[mask] = min(dp[mask], max(dp[sub], diam[rest]));
        }
    }
    printf("%lld\n", dp[(1 << N) - 1]); // ⑤ 全集的最优划分
}

逐行解析：

① 对每个子集 $S$ ，遍历所有点对，求最大距离平方。 $2^N \times N^2 \approx 7M$ 。
③ 不分割时，整个 mask 就是一组，代价是 diam[mask]。
④ 枚举子集：sub = (sub-1) & mask 是枚举子集的经典写法。把 mask 分成 sub 和 rest 两部分，代价取较大的那个。
⑤ 答案是全集（所有位为 1）的最优划分。注意这个 DP 不限制恰好 $K$ 组——但多分一组不会更差（单元素组的 diam=0），所以至少分 $K$ 组的最优解一定包含了恰好 $K$ 组的解。

验证： $N=3, K=2$ ，点 $P_0=(0,1), P_1=(1,2), P_2=(2,0)$ 。

子集距离平方：{0,1}→ $(0-1)^2+(1-2)^2=2$ , {0,2}→ $(0-2)^2+(1-0)^2=5$ , {1,2}→ $(1-2)^2+(2-0)^2=5$ 。

dp[{0,1}] = 2, dp[{0,2}] = 5, dp[{1,2}] = 5。dp[{0,1,2}]：分 {0,1}+{2} → max(2,0)=2；分 {0,2}+{1} → max(5,0)=5；分 {1,2}+{0} → max(5,0)=5。答案 = 2。✓（样例 1 的输出也是 2）

例题 3：T90 063 — Monochromatic Subgrid（★4，行子集枚举）

题目： $H \times W$ 的网格，每个格子是 0 或 1。选若干行，取这些行的交集（所有选中行都为 1 的列）。求最大交集大小。

数据范围： $1 \le H \le 8$ ， $1 \le W \le 10^4$

—— AtCoder Typical 90 063

分析： $H \le 8$ ，枚举所有 $2^H = 256$ 种行子集。对每种子集，检查哪些列在所有选中行中都是 1。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int H, W;
    scanf("%d%d", &H, &W);
    int g[8][10004];
    for (int i = 0; i < H; i++)
        for (int j = 0; j < W; j++) scanf("%d", &g[i][j]);

    int ans = 0;
    for (int mask = 1; mask < (1 << H); mask++) { // ① 枚举行子集
        int cnt = 0;
        for (int j = 0; j < W; j++) {
            bool ok = true;
            for (int i = 0; i < H; i++)
                if ((mask >> i & 1) && g[i][j] == 0) ok = false; // ② 该行有 0
            if (ok) cnt++; // ③ 所有选中行此列都为 1
        }
        int rows = __builtin_popcount(mask);
        ans = max(ans, rows * cnt); // ④ 选中行数 × 交集大小
    }
    printf("%d\n", ans);
}

逐行解析：

① 枚举所有非空行子集， $2^H \le 256$ 。
② 对每一列 $j$ ，检查所有选中行 $i$ 是否在该列都是 1。
④ 选中行数 __builtin_popcount(mask) 乘以交集列数。

例题 4：T90 086 — Snuke’s Favorite Arrays（★5，逐位 bitmask 构造）

题目：构造长度 $N$ 的非负整数数组 $A$ ，满足 $Q$ 个约束。每个约束给出 $(X_i, Y_i, Z_i, W_i)$ ，要求 $A_{X_i} \text{ OR } A_{Y_i} \text{ OR } A_{Z_i} = W_i$ 。求方案数，对 $10^9+7$ 取模。

数据范围： $3 \le N \le 12$ ， $1 \le Q \le 50$

—— AtCoder Typical 90 086

分析：逐位独立处理。对于每一位 $b$ （0 到 59）， $A_i$ 在第 $b$ 位要么是 0 要么是 1。每个约束要求 $A_{X_i} \text{ OR } A_{Y_i} \text{ OR } A_{Z_i}$ 在第 $b$ 位等于 $W_i$ 的第 $b$ 位。

$N \le 12$ ，可以用 bitmask 枚举每个位置在该位的 0/1 赋值。

代码（逐位处理，每位独立计数再相乘）：

#include <cstdio>
using namespace std;

int X[59], Y[59], Z[59];
long long W[59];

int main() {
    int N, Q;
    scanf("%d%d", &N, &Q);
    for (int i = 0; i < Q; i++) scanf("%d%d%d%lld", &X[i], &Y[i], &Z[i], &W[i]);
    for (int i = 0; i < Q; i++) { X[i]--; Y[i]--; Z[i]--; }

    const int MOD = 1000000007;
    long long ans = 1;

    for (int b = 0; b < 60; b++) { // ① 逐位处理
        long long cnt = 0;
        for (int mask = 0; mask < (1 << N); mask++) { // ② 枚举该位的赋值
            bool ok = true;
            for (int i = 0; i < Q; i++) { // ③ 检查所有约束
                int val = ((mask >> X[i]) & 1) | ((mask >> Y[i]) & 1) | ((mask >> Z[i]) & 1); // ④ OR 运算
                int target = (W[i] >> b) & 1;
                if (val != target) { ok = false; break; }
            }
            if (ok) cnt++;
        }
        ans = ans * cnt % MOD; // ⑤ 各位独立，方案数相乘
    }
    printf("%lld\n", ans);
}

逐行解析：

① 每个二进制位独立处理。OR 运算逐位不互相影响。
② 枚举 $N$ 个元素在该位的 0/1 赋值， $2^N \le 4096$ 种。
③ 对每个约束，计算 A[X] OR A[Y] OR A[Z] 在该位的值。
④ 用 |（位或）而非 &（位与）。三位置的 OR 结果与 $W_i$ 的该位比较。
⑤ 60 位各自的合法赋值数相乘（各位独立）。

参考文献

教材讲解 — 競技プログラミングの鉄則第 4 章

4.8 B23 Traveling Salesman Problem（bitmask DP/TSP 解说）

系统练习 — 競技プログラミングの鉄則

B23 Traveling Salesman Problem（TSP 模板）【例题】

实战练习 — 競プロ典型 90 問

系列索引

第零章基础工具

第一章搜索技术

第二章数学基础

第三章数据结构

第四章图论

第五章动态规划

第六章贪心

第七章字符串

第八章进阶

状态压缩DP

N 个物品选不选用 N 位二进制编码——从 N! 暴力降到 2^N × N 的状态空间

前言

问题的本质

从排列到子集

bitmask 操作速查

状态设计

理论 + 代码

TSP 完整实现

例题

例题 1：TB B23 — Traveling Salesman Problem

例题 2：T90 045 — Simple Grouping（★6， bitmask 分组）

例题 3：T90 063 — Monochromatic Subgrid（★4，行子集枚举）

例题 4：T90 086 — Snuke’s Favorite Arrays（★5，逐位 bitmask 构造）

参考文献

系列索引

状态压缩DP