状压DP与子集枚举：位运算优化算法实战-平芜编程栈

1. 状压DP与子集枚举的核心概念

第一次接触状压DP时，我被这种将集合状态压缩为二进制数的巧妙思路震撼到了。想象你面前有n个物品，每个物品有"选"或"不选"两种状态，传统方法可能需要一个n维数组来表示所有组合，而状压DP仅用一个整数的二进制位就能完美表达。

位运算在状压DP中扮演着关键角色。当我们需要表示集合{1,3,4,8}时，可以将其编码为二进制数100011010（从右往左数第1、3、4、8位为1）。这种表示法的空间效率极高——一个32位整数就能处理32个元素的集合问题。

2. 位运算技巧深度解析

2.1 基础位运算操作

在实战中，这些位运算操作必须烂熟于心：

集合交集：a & b
集合并集：a | b
集合补集：~a（注意整数位数）
集合差集：a & (~b)
对称差集：a ^ b

一个容易踩的坑是位运算的优先级。记得在一次比赛中，我写了if (state & mask == target)，结果总是出错。后来发现==优先级高于&，正确写法应该是if ((state & mask) == target)。

2.2 高效枚举子集的技巧

最令人惊叹的是这个枚举子集的魔法代码：

for(int subset = set; subset; subset = (subset-1) & set) { // 处理subset }

这个循环会按降序枚举set的所有非空子集。比如对于set=0b1011，它会依次产生：1011、1010、1001、1000、0011、0010、0001。原理在于(subset-1) & set这个操作会：

将当前subset的最低位1变为0
将该位右侧所有0变为1
只保留原set中存在的1

3. 状压DP的经典应用场景

3.1 旅行商问题(TSP)的优化

传统TSP解法时间复杂度是O(n!)，而状压DP可以优化到O(n²2ⁿ)。定义dp[mask][u]表示：

mask：已访问城市集合（二进制表示）
u：当前所在城市

状态转移方程：

dp[mask][u] = min(dp[mask][u], dp[mask^(1<<u)][v] + dist[v][u])

实际编码时要注意：

先枚举mask再枚举u，保证子问题已计算
使用位运算快速判断城市是否已访问

3.2 棋盘覆盖问题

比如用多米诺骨牌覆盖棋盘，每个位置有"已覆盖"和"未覆盖"两种状态。通过将每行的状态压缩为一个整数，可以逐行进行DP转移。这类问题通常需要：

预处理所有合法的单行状态
检查相邻行状态的兼容性

4. 时间复杂度分析与优化

4.1 常见复杂度模型

状压DP的时间复杂度通常包含2ⁿ因子：

单纯状态枚举：O(2ⁿ)
枚举子集：O(3ⁿ) （每个元素有3种状态：不在集合/在集合不在子集/在子集）
带附加维度：O(n²2ⁿ)（如TSP问题）

4.2 实测性能对比

在我的笔记本上测试不同规模问题的运行时间：

n=15: 约0.5秒 n=20: 约30秒 n=25: 超过10分钟

因此在实际比赛中，n≤20是较安全的上限。当n≥25时，可能需要考虑剪枝或启发式算法。

5. 竞赛中的实战技巧

5.1 预处理合法状态

对于某些限制严格的问题（如互不攻击的棋子摆放），提前生成所有合法状态可以大幅加速DP过程。例如：

vector<int> valid_states; for(int mask=0; mask<(1<<n); ++mask){ if(!(mask & (mask>>1))) // 检查是否有相邻1 valid_states.push_back(mask); }

5.2 滚动数组优化

当DP状态只依赖前一行时，可以使用滚动数组将空间复杂度从O(2ⁿ)降到O(1)。关键代码：

int dp[2][1<<n]; bool cur = 0; for(int i=0; i<m; ++i){ cur ^= 1; memset(dp[cur], 0, sizeof(dp[cur])); // 状态转移... }

5.3 调试技巧

调试状压DP时，这些方法很实用：

将状态转换为二进制字符串：

bitset<10> bs(state); cout << bs << endl;

使用__builtin_popcount()快速计算集合大小
预先计算log2表，方便通过状态反推元素

6. 从子集枚举到高维前缀和

6.1 SOS DP（Sum Over Subsets）

这是一种高效计算子集和的技术，能在O(n2ⁿ)时间内求出所有状态的子集和。核心思想是分维度处理：

for(int i=0; i<n; ++i) for(int mask=0; mask<(1<<n); ++mask) if(mask & (1<<i)) dp[mask] += dp[mask^(1<<i)];

6.2 应用案例：包含特定元素的子集计数

给定数组a和多个查询(x,k)，询问有多少子集的AND结果第x位为1，且子集大小=k。使用SOS DP可以预处理后O(1)回答每个查询。

7. 常见错误与验证方法

在多次实战中，我总结出这些易错点：

位运算优先级混淆：总是加括号
整数溢出：使用1LL<<n而不是1<<n当n≥32
初始状态设置错误：特别是空集情况
循环顺序不当：确保子问题先于父问题求解

验证DP正确性的一个好方法是手工计算小规模案例。比如n=3时，手动枚举所有8种状态，核对DP结果是否匹配。

8. 进阶技巧：对称性优化

当问题具有对称性时，可以大幅减少状态数。例如在棋盘问题中，旋转对称的状态可以视为等价类。实现时通常需要：

设计规范化表示
预处理等价类代表元
调整转移方程考虑对称性

9. 与其他算法的结合应用

9.1 状压DP+双指针

某些问题需要同时处理两个状态集合的交互。例如：

int l=0, r=(1<<n)-1; while(l <= r){ if(check(l, r)) ans++; // 移动指针... }

9.2 状压DP+Meet in Middle

当n较大时(如n=40)，可以将集合分成两半分别处理，再合并结果。这能将O(2ⁿ)降为O(2^(n/2))。

10. 实战代码框架

最后分享我的状压DP通用模板：

const int MAXN = 20; int dp[1<<MAXN]; int solve() { memset(dp, 0x3f, sizeof(dp)); // 初始化为INF dp[0] = 0; // 初始状态 for(int mask=0; mask<(1<<n); ++mask){ if(dp[mask] == INF) continue; // 生成新状态new_mask for(...){ int new_mask = mask | (...); dp[new_mask] = min(dp[new_mask], dp[mask] + cost); } } return dp[(1<<n)-1]; }

关键点：