C++位运算的妙用：状态压缩DP入门

C++动态规划（DP）是算法竞赛的灵魂，而状态压缩DP（简称状压DP）则是在 DP 中加入了“位运算”这一利器，将复杂的集合状态用一个整数表示，从而在指数级的状态空间中找到多项式时间（通常是 O(2^n·n)）的解法。状态压缩DP常见于旅行商问题（TSP）、集合覆盖、N皇后变种等场景。本文将从位运算基础讲起，通过经典例题带你入门状压DP，领略二进制操作的魅力。

一、为什么需要状态压缩？

在很多DP问题中，状态往往涉及“哪些元素已经用过”或“哪些位置被占据”。如果我们用布尔数组标记，状态表示复杂且无法直接作为数组下标。此时，如果元素个数 n 较小（通常 n ≤ 20），我们可以用一个整数的二进制位来表示集合：第 i 位为 1 表示元素 i 已选（或存在），0 表示未选。这样，一个 int 或 long long 就能容纳所有子集，状态总数从无法枚举变为 2^n 个，配合递推或记忆化搜索即可求解。

二、位运算基础（必会）

在 C++ 中，整数的二进制位运算高效且直观。以下是状压DP中最常用的操作（假设 mask 是一个整数，n 位有效）：

三、入门例题：最短哈密顿路径（TSP雏形）

问题描述：给定 n 个点（n ≤ 20）和点之间的距离矩阵 dist[i][j]，求从起点 0 出发，经过所有点恰好一次，最后到达终点 n-1 的最短路径长度。

分析：状态需要知道“哪些点已经访问过”以及“当前在哪个点”。定义 dp[mask][i] 表示已经访问过的点集合为 mask，当前位于点 i 时的最短路径长度。转移时，从点 i 走到一个尚未访问的点 j，更新 dp[mask | (1<<j)][j]。最终答案为 dp[(1<<n)-1][n-1]。

C++ 实现：

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int dist[20][20];
int dp[1<<20][20];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> dist[i][j];
    
    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0;  // 从点0出发，只访问了点0
    
    for (int mask = 1; mask < (1<<n); ++mask) {
        for (int i = 0; i < n; ++i) if ((mask >> i) & 1) {
            if (dp[mask][i] == INF) continue;
            for (int j = 0; j < n; ++j) if (!((mask >> j) & 1)) {
                int newMask = mask | (1<<j);
                dp[newMask][j] = min(dp[newMask][j], dp[mask][i] + dist[i][j]);
            }
        }
    }
    
    int ans = dp[(1<<n)-1][n-1];
    cout << (ans == INF ? -1 : ans) << endl;
    return 0;
}

复杂度：状态数 2^n × n，转移 O(n)，总 O(2^n·n²)。当 n=20 时，约 4e8 次运算，在 C++ 优化下勉强可过。可以进一步优化：只遍历 mask 中为 1 的 i，并且 j 枚举未被访问的点。

四、进阶技巧：枚举子集

有些问题需要枚举当前状态的所有子集。例如：给一个集合，将其划分成若干子集，求某种代价最小值。直接枚举子集可以做到 O(3^n)。

模板：

for (int mask = 0; mask < (1<<n); ++mask) {
    // 枚举 mask 的所有非空子集 sub
    for (int sub = mask; sub; sub = (sub-1) & mask) {
        // 处理子集 sub
    }
}

原理：(sub-1) & mask 会得到 mask 的下一个更小的子集，直到 0。

五、常见状态压缩DP模型

1. 独立集/覆盖问题

给定图 G，求最大权独立集（选出的点互不相邻）。状态 dp[mask] 表示 mask 集合是否独立，再在此基础上 DP 或直接枚举。

2. 分配问题（如任务分配）

n 个人做 n 项任务，效率矩阵 cost[i][j]，每人一项，最小化总代价。dp[mask] 表示前 k 个人（k = popcount(mask)）分配了 mask 任务集合的最小代价，转移时第 k 个人尝试所有未分配的任务。复杂度 O(n·2^n)。

3. 棋盘覆盖（如放车、N皇后变种）

用二进制表示每行的放置状态，逐行转移。

六、位运算优化技巧

• 使用 __builtin_popcount(mask)：GCC 内置函数，快速计算 1 的个数，用于知道已选了几个元素。

• 预先计算所有子集的权值：如果经常需要对某个子集求和，可以提前预处理 sum[mask]，避免重复计算。

• lowbit 迭代：用于快速遍历 mask 中所有 1 的位置：

  cpp

  for (int t = mask; t; t -= t & -t) {
      int i = __builtin_ctz(t); // 低位0的个数，即位置
  }

• 滚动数组：当 DP 的某一维只依赖前一层时，可以压缩掉一维。

七、实战案例：洛谷 P1171 售货员的难题

这是经典的 TSP 问题，n ≤ 20。用上面的 DP 模板可以直接 AC。但有一个常见错误：初始状态 dp[1][0]=0 只保证了从 0 出发，但最终要求回到起点？原题往往不要求回到起点，只要求走完所有点。如果需要回到起点，可最后加 dist[i][0]。

八、何时使用状态压缩DP？

• n ≤ 20 左右（2^n ≤ 1,048,576，配合 n 因子约 2e7 运算，可接受）。

• 状态可以用集合简洁表示，且集合交集、并集、子集操作频繁。

• 难以用其他经典算法（如网络流、贪心）求解。

九、注意事项

1. 数组大小：dp[1<<n][n]，当 n=20 时需要约 20 * 2^20 ≈ 20MB（int 类型），若 n=21 则翻倍，可能会 MLE，可以改用 short 或滚动维。

2. 初始化和 INF：使用 0x3f3f3f3f 作为无穷大，两个相加不会溢出（小于 0x7fffffff）。

3. 状态转移顺序：通常按 mask 从小到大（因为新 mask 一定包含更多位，数值更大），也可以使用记忆化搜索。

4. 边界条件：注意起点和终点的特殊要求。

十、总结与展望

状态压缩DP将集合的指数级可能性融入 DP 框架，是解决小规模组合优化问题的利器。位运算则让状态操作变得简洁且高效。掌握状压DP，你就能解决诸如 TSP、集合划分、精确覆盖等问题——这些题目在竞赛中往往是区分选手的分水岭。

学完本文后，建议你立即动手实现以下题目：

• 洛谷 P1433 吃奶酪（TSP 变种）

• 洛谷 P1896 [SCOI2005] 互不侵犯（棋盘状压）

• POJ 2288 Islands and Bridges（带权值的 TSP）

当你完成几道状压DP题后，你会惊叹于位运算的优美和 DP 的强大。记住：状态压缩不仅仅是一种技巧，更是一种思维方式——用二进制看世界。