第 103B 章 状压 DP¶
状压动态规划（状态压缩动态规划）的状态载体是集合：用一个整数的二进制位表示「哪些元素已经选了」， 「最后一步」是加入哪个元素、或者上一行是什么。
规模由 \(n\) 卡死：\(O(2^n n)\) 到 \(n \le 20\)，枚举子集的 \(O(3^n)\) 到 \(n \le 15\)。 Python 在这里有一个别处没有的便宜——大整数天然就是 bitset， 超过 64 位的集合照样位运算，而且走的是 C 层。
同源的另外三种形态：区间 DP、树形 DP、DAG 上的 DP。
计数版本：把 \(\min\)/\(\max\) 换成 \(+\) 就是计数 DP，取模的时机与陷阱见 DP 入门 · 计数 DP 与取模。
用一个整数的二进制位表示「集合」，状态是这个整数。
适用条件：集合元素个数 \(n \le 20\) 左右（\(2^{20} \approx 10^6\) 个状态）。
1 常用位操作¶
见 位运算，这里列出状压 DP 专用的：
# [片段]
(mask >> i) & 1 # 第 i 个元素是否在集合里：把第 i 位挪到最低位再取出
mask | (1 << i) # 加入元素 i：或运算只会把该位置 1，其余位不动
mask & ~(1 << i) # 移除元素 i：取反后该位为 0，与运算把它清掉
mask & (mask - 1) # 移除最低位的 1：减一会翻转最低位 1 及其右边的全部 0
bin(mask).count("1") # 集合大小（3.9 写法；3.10+ 用 mask.bit_count()）
# 枚举 mask 的所有子集（含空集），O(2^popcount)
sub = mask # 从全集出发，逐个变小地枚举
while True:
... # 处理 sub
if sub == 0: # 空集也要处理，所以判空放在处理之后
break
sub = (sub - 1) & mask # 减一借位后再与 mask，跳到下一个更小的子集
枚举所有 mask 的所有子集，总复杂度是 \(O(3^n)\) 而不是 \(O(4^n)\)—— 每个元素有「在 mask 且在 sub」「在 mask 不在 sub」「不在 mask」三种状态。 \(n = 16\) 时 \(3^{16} \approx 4.3\times10^7\)，Python 下已经不行了。
2 两类经典状压¶
类型一：集合是「已选过哪些元素」
旅行商问题（TSP）：\(f[\text{mask}][i]\) = 走过集合 mask、当前在 \(i\) 的最短路。 \(O(2^n n^2)\)，\(n \le 15\) 时 Python 可行（\(7.4\times10^6\)）。
类型二：集合是「一行的状态」（棋盘类）
逐行推进，\(f[i][\text{mask}]\) = 前 \(i\) 行、第 \(i\) 行状态为 mask 的最优值。 行内合法性与行间兼容性都用位运算一次判完：
# [片段]
mask & (mask << 1) == 0 # 行内不相邻：左移一位后无公共 1
(m1 | (m1 << 1) | (m1 >> 1)) & m2 == 0 # 行间不相邻（含斜向）
# 上一行的每个 1 向左右各扩一位，覆盖正下方与两个斜下方，再与本行取交
solutions/nowcoder/BISHI79/sol.py（取数游戏）用的正是这个套路。
3 Python 下的状压优化¶
| 手段 | 说明 |
|---|---|
| 预处理合法 mask 列表 | 先筛出行内合法的 mask，循环只跑这些（通常远少于 \(2^n\)） |
| 预处理兼容表 | ok[m1] = 与 \(m_1\) 兼容的 mask 列表，避免内层重复位运算 |
用 list 而不是 dict 存 \(f\) |
mask 是连续整数下标，list 快 2–3 倍 |
| 大整数当位集合 | 当「集合」超过 64 位时，Python 大整数天然是无限位 bitset，位运算走 C 层 |
最后一条是 Python 的独有优势：
solutions/nowcoder/BISHI4/sol.py的两级值域位图就是这个思路的极致运用， 见 平衡树与有序集合。
4 本章速查¶
| 形态 | 状态载体 | 枚举顺序 | 「最后一步」是什么 |
|---|---|---|---|
| 状压 DP | 集合 mask | mask 从小到大（子集先于超集） | 加入哪个元素 / 上一行是什么 |
| Python 关键 | 做法 |
|---|---|
| 状压枚举子集 | sub = (sub - 1) & mask，总量 \(O(3^n)\)，\(n \le 15\) 为限 |
| 状压存储 | 用 list 不用 dict |
| 超 64 位集合 | Python 大整数天然是 bitset，位运算走 C 层 |
| 规模判据 | Python |
|---|---|
| 状压 \(O(2^n n)\) | \(n \le 20\) ✅ |
| 状压 \(O(3^n)\) | \(n \le 15\) ✅、\(n = 16\) ❌ |