别再被Cartographer的.lua配置文件搞懵了！手把手教你从雷达/IMU启动文件到revo_lds.lua的完整配置流程
2026/6/15 1:49:55
引言
在动态规划中，状态的表示直接影响算法的可行性与效率。当问题涉及“集合覆盖”“子集选择”“排列顺序”等组合对象时，直接用数组下标表示集合往往需要指数级空间。状态压缩DP（简称状压DP）利用二进制位来表示集合的状态（0/1表示元素是否在集合中），从而将复杂的状态空间压缩为一个整数，再用DP递推求解。
如果把普通DP比作“用表格填数字”，那么状压DP就是“用二进制密码本记录集合，一次位运算就完成状态转移”—— 它以位的代价，换取了表达指数级组合的能力。
前置知识
位运算基础：
&（与）、|（或）、^（异或）、<<（左移）、>>（右移）、~（取反）。常用位运算技巧：
取出第
i位：(s >> i) & 1将第
i位设为1：s | (1 << i)将第
i位设为0：s & ~(1 << i)枚举所有子集：
for (int sub = s; sub; sub = (sub-1) & s)判断是否是2的幂：
(s & (s-1)) == 0
动态规划基础：状态定义、转移方程、初始条件、答案提取。
核心思想
状压DP的核心在于：将集合用整数表示，整数的二进制位对应集合中的元素（通常元素个数 n ≤ 20，因为 2^n 状态数可接受）。例如：
n = 4 时，整数
5=0101（二进制）表示第0和第2个元素在集合中。状态总数最多 2^n，当 n=20 时约 100 万，可以接受。
典型模型：
旅行商问题（TSP）：
dp[mask][u]表示已经访问过的城市集合为 mask，当前在城市 u 时的最短路径。覆盖问题：
dp[mask]表示覆盖集合 mask 所需的最小代价。子集枚举DP：
dp[mask] = min(dp[mask], dp[sub] + cost(sub ^ mask))等。
形象地讲：状压DP就是把“哪些元素用过了”这个信息，写在了一个整数的二进制位里。转移时不再需要遍历元素列表，而是直接用位运算判断、取反、取子集。
算法步骤（以TSP为例）
状态定义：
dp[mask][u]= 已经访问过集合 mask 中的城市，最后停留在城市 u 的最短距离。初始化：
dp[1 << start][start] = 0，其余为无穷大。转移：对于每个状态
(mask, u)，尝试走到下一个未访问的城市 v：if ((mask >> v) & 1) == 0: new_mask = mask | (1 << v); dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + dist[u][v]);
答案：
min(dp[(1<<n)-1][u] + dist[u][start])回到起点的最小环路。
代码框架：
int n; int dist[N][N]; int dp[1<<N][N]; int tsp() { memset(dp, 0x3f, sizeof(dp)); dp[1][0] = 0; // 从0号城市出发 for (int mask = 1; mask < (1<<n); ++mask) { for (int u = 0; u < n; ++u) if ((mask >> u) & 1) { for (int v = 0; v < n; ++v) if (!((mask >> v) & 1)) { int new_mask = mask | (1 << v); dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + dist[u][v]); } } } int ans = INF; int full = (1 << n) - 1; for (int u = 0; u < n; ++u) { ans = min(ans, dp[full][u] + dist[u][0]); } return ans; }复杂度与性质
| 特征 | 说明 |
|---|---|
| 时间复杂度 | O(2^n * n²) 或 O(2^n * n) 取决于内层循环 |
| 空间复杂度 | O(2^n * n) |
| 适用规模 | n ≤ 20 通常可接受，n=25 时 2^25≈3300万，需优化 |
| 常用优化 | 预处理合法转移、只遍历包含u的状态、使用滚动数组 |
性质：
状压DP常用于NP-hard问题的精确求解（如TSP、集合覆盖），对于小规模数据非常有效。
可以与递推、记忆化搜索结合。
可以利用对称性、剪枝减少状态。
子集卷积、快速沃尔什变换（FWT）可用于加速某些状压DP的转移。
例题与解析
例题1：旅行商问题（TSP，Luogu P1171）
题目描述
有 n（n ≤ 20）个城市，给出城市间的距离矩阵（对称，不满足三角不等式）。求从城市0出发，访问所有城市恰好一次并返回城市0的最短路径长度。
输入示例
4 0 2 6 5 2 0 4 4 6 4 0 2 5 4 2 0
输出示例
13
解题思路
直接使用上述TSP的状压DP模板，注意距离矩阵可能不是对称的，但题目保证对称。注意边界条件：从0出发，最终回到0。
解析
状态总数 2^n * n ≈ 2^20 * 20 ≈ 2000万，在C++中勉强可过（需要常数优化）。
可以使用滚动数组只保留当前mask的dp值，但转移需要枚举u和v，无法完全滚动。常用的优化是只对
mask中已经访问过的u进行转移，并且预先存储每个mask有哪些u（通过lowbit迭代）。或者使用递推顺序：for mask从1到full，内层for u枚举，再内层for v枚举未访问点。
例题2：玉米田（Luogu P1879）
题目描述
农夫有一块 n×m（n,m ≤ 12）的网格，某些格子是贫瘠的（不能种玉米），某些是肥沃的。要种玉米，要求相邻（上下左右）的格子不能同时种。求有多少种种植方案（模100000000）。
输入示例
2 3 1 1 1 0 1 0
输出示例
9
解题思路
每一行的种植状态可以用一个 m 位二进制数表示（1表示种，0表示不种）。
预处理该行自身是否合法（不能有相邻的1，且不能种在贫瘠格子上）。
相邻两行状态不能有在同一列都是1（即
state & prev_state == 0）。定义
dp[i][state]表示前 i 行，第 i 行状态为 state 的方案数。转移：
dp[i][state] = sum(dp[i-1][prev])其中(state & prev) == 0且两者都合法。
解析
总状态数最多 2^12 = 4096，行数12，复杂度 O(n * 2^m * 2^m) ≈ 12 * 4096 * 4096 ≈ 2亿，稍大但通过预处理合法状态可优化。合法状态数量远小于 2^m（因为相邻不能为1，斐波那契数约为 2^m / φ^m）。
典型轮廓线DP（插头DP）的简化版。
例题3：互不侵犯（Luogu P1896）
题目描述
在 n×n（n ≤ 9）的棋盘上放 k 个国王，国王的攻击范围是周围8个格子。求互不攻击的摆放方案数。
输入示例
3 2
输出示例
16
解题思路
每一行状态用二进制表示国王的放置情况。
需要预处理：一行内不能有相邻的国王（
state & (state<<1) == 0）。相邻两行之间不能有冲突：
(state & prev) == 0且(state & (prev<<1)) == 0且(state & (prev>>1)) == 0。定义
dp[i][state][c]表示前 i 行，第 i 行状态为 state，已经放置了 c 个国王的方案数。转移时累加前一行的合法状态，增加国王数。
解析
相比玉米田多了“对角线”限制，以及国王数量的维度。
n=9，状态最多 2^9=512，国王数最多 81，DP数组大小 10*512*82 ≈ 42万，可接受。
拓展
轮廓线DP（插头DP）：处理棋盘上的连通性问题（如铺砖、哈密顿路径），状态是轮廓线上的连通性表示（括号序列或最小表示法）。
子集DP（SOS DP）：用于快速处理子集求和、子集最值等问题，复杂度 O(n·2^n)。
DP on subsets with FWT：利用快速沃尔什变换加速子集卷积，用于某些集合划分问题。
记忆化搜索+状态压缩：对于不确定的转移顺序，用DFS+备忘录代替递推。
总结
状压DP将组合问题的指数级可能性压缩在整数位中，配合位运算，使得原本无法处理的集合划分、子集选择问题在小规模上变得可行。它是算法竞赛中解决NP-hard问题的经典武器，也是理解更复杂DP（如插头DP、子集卷积）的基础。