企业官网建设流程全解析

1. 从两个经典题看状压DP到底在解决什么问题

状压DP这个知识点，很多人第一次接触的时候会觉得“名字挺唬人”，但真正理解之后会发现它其实是一种非常朴素的暴力优化思路。我第一次系统刷这两个题——蒙德里安的梦想和最短Hamilton路径——是在刚学完基础DP之后，当时最大的困惑就是：为什么有的DP用一维数组就能搞定，有的却要开一个2的n次方那么大的数组？后来踩了几次坑才明白，状压DP的核心适用场景就一个：状态本身是一个集合，而集合的元素个数不多（通常不超过20个），我们需要在状态之间做转移。

蒙德里安的梦想是AcWing 291题，最短Hamilton路径是AcWing 91题，这两个题在算法竞赛圈里几乎是状压DP的“入门双壁”。前者让你理解“轮廓线”和“状态合法性预处理”的思想，后者让你掌握“集合DP”的标准转移框架。把这两个题吃透，后面再遇到什么“炮兵阵地”“玉米田”“宝藏”之类的状压题，基本都能找到切入点。

这篇文章我会从零开始拆解这两个题的思路、实现细节、优化技巧和常见坑点。不管你是刚学状压DP的新手，还是刷过几道题但总觉得理解不透的进阶选手，应该都能从中找到对自己有用的东西。全文会涉及大量代码和推导，建议边看边在纸上画一画状态转移的过程，效果会好很多。

2. 状压DP的前置知识：位运算与状态表示

2.1 为什么用二进制表示集合

在讲具体题目之前，有必要先把“状压”这个概念的底层逻辑说清楚。假设我们有一个包含n个元素的集合，每个元素只有“选”或“不选”两种状态，那么整个集合的状态就可以用一个n位的二进制数来表示。比如n=5时，二进制数10110表示第1、2、4号元素被选中（从右往左数，下标从0开始）。

这样做的好处非常直接：一个整数就能承载整个集合的信息，而且集合的合并、判断、枚举都可以用位运算在O(1)时间内完成。对比一下，如果用布尔数组存集合，判断两个集合是否有交集需要O(n)时间，而用二进制只需要a & b一步到位。

常用的位运算操作我整理成了一张表，这些在状压DP里会反复用到：

注意：位运算的优先级普遍低于比较运算符，写代码时该加括号就加括号，s & 1 == 1这种写法是错的，必须写成(s & 1) == 1。这个坑我见过太多人中招。

2.2 状压DP的状态设计套路

状压DP的状态设计有一个比较固定的模式：dp[阶段][状态]，其中状态是一个二进制数。阶段可以是“处理到第几行”“已经走过哪些点”“当前停在哪个位置”等等，具体看题目要求。

转移的时候，通常有两种方式：一种是“从当前状态推出去”，枚举下一个可以加入的元素；另一种是“从之前的状态收进来”，枚举当前状态是由哪些状态转移来的。两种方式等价，但有时候其中一种写起来更顺手。蒙德里安的梦想适合用“推出去”的方式，最短Hamilton路径适合用“收进来”的方式，后面会详细讲。

状态数一般是2^n，转移的复杂度取决于每个状态能转移到多少个其他状态。如果每个状态要枚举所有其他状态，总复杂度就是O(2^n * 2^n)，n=20时大约是10的12次方，肯定超时。所以状压DP的关键优化就在于：通过预处理减少无效转移，或者用子集枚举把复杂度降到O(3^n)。

3. 蒙德里安的梦想：轮廓线与状态合法性预处理

3.1 题目核心需求拆解

蒙德里安的梦想原题描述是这样的：给定一个N×M的棋盘，要求用1×2的多米诺骨牌完全覆盖，问有多少种不同的覆盖方案。N和M的范围通常是一个较小（比如N≤11），另一个可以稍大（M≤11），因为状态数取决于较小的那一维。

这个题的本质是棋盘覆盖计数问题。为什么它能用状压DP做？因为当我们逐列（或逐行）填充骨牌时，当前列的填充情况只和上一列的“突出”情况有关，而每一列的填充情况可以用一个二进制数表示——某一位为1表示这一列的这个位置被上一列横放的骨牌占用了。

我第一次做这个题的时候，最大的困惑是：为什么状态要按列来定义，而不是按格子？后来想明白了，因为骨牌的尺寸是1×2，横放的骨牌会跨越两列，竖放的骨牌只在一列内。如果我们逐列处理，那么横放骨牌的影响就变成了“上一列伸到当前列”的一个标记，这个标记正好可以用二进制表示。

3.2 状态定义与转移方程推导

设dp[i][j]表示前i-1列已经填满，且第i列的状态为j的方案数。这里的j是一个N位的二进制数，j的第k位为1表示第i列的第k行被上一列横放的骨牌占据了。

为什么是“前i-1列已经填满”？因为我们在逐列推进的时候，必须保证之前的列不能再有空位，否则后面没法补。而第i列的状态j记录了它被上一列“侵入”的情况，这些位置在当前列已经被占了，不能再放其他骨牌。

转移的时候，我们枚举第i+1列的状态k，判断从j能否转移到k。转移合法的条件有两个：

第一，j和k不能在同一行同时为1。因为如果j的第r位为1，说明第i列第r行已经被上一列占了；如果k的第r位也为1，说明第i+1列第r行被第i列横放的骨牌占了，但第i列第r行本身已经被占了，不可能再放一个横放骨牌伸出去。所以必须满足(j & k) == 0。

第二，第i列中那些没有被j占用的位置（即j的二进制中为0的位），必须能够用竖放的骨牌填满。也就是说，这些连续的空位长度必须是偶数。如果存在奇数长度的连续空位，就无法用竖放骨牌填充。这个条件需要对j | k做一次合法性检查。

所以转移方程是：

dp[i+1][k] += dp[i][j] (当 (j & k) == 0 且 j | k 是合法状态)

最终答案是dp[M][0]，即第M+1列没有任何被侵入，前M列全部填满。

3.3 合法性预处理的实现细节

上面提到的“j | k是合法状态”这个判断，如果每次转移都现场算一遍，复杂度会比较高。标准做法是预处理出所有“合法状态”——即二进制表示中不存在奇数长度连续0的状态。预处理的代码如下：

// 预处理所有合法状态 for (int s = 0; s < (1 << N); s++) { int cnt = 0; // 当前连续0的个数 bool valid = true; for (int i = 0; i < N; i++) { if ((s >> i) & 1) { // 遇到1，检查之前的连续0是否为奇数 if (cnt & 1) { valid = false; break; } cnt = 0; } else { cnt++; } } if (cnt & 1) valid = false; // 检查末尾的连续0 st[s] = valid; }

这段代码的逻辑很直白：从左到右扫描每一位，遇到1就检查前面累积的连续0个数是否为奇数，最后还要检查末尾的连续0。cnt & 1等价于cnt % 2 == 1，用位运算更快。

预处理之后，转移的时候只需要判断st[j | k]是否为true即可。这一步优化能把复杂度从O(M * 4^N * N)降到O(M * 4^N)，虽然4^N还是很大，但N通常不超过11，4^11大约是400万，乘以M（也约11）就是4400万，在C++里跑起来问题不大。

实操心得：如果N和M中有一个明显更小，一定要把小的那个作为状态维度。比如N=11, M=11时无所谓，但如果N=5, M=100，那状态数只有2^5=32，复杂度直接降到可以忽略不计。我见过有人不判断大小直接写，结果TLE了还在找原因。

3.4 完整代码与逐行注释

#include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 12, M = 1 << N; long long dp[N][M]; // dp[i][j]: 前i-1列填满，第i列状态为j的方案数 bool st[M]; // st[s]: 状态s是否合法（无奇数长度连续0） int main() { int n, m; while (cin >> n >> m, n || m) { // 预处理合法状态 for (int s = 0; s < (1 << n); s++) { int cnt = 0; bool valid = true; for (int i = 0; i < n; i++) { if ((s >> i) & 1) { if (cnt & 1) { valid = false; break; } cnt = 0; } else { cnt++; } } if (cnt & 1) valid = false; st[s] = valid; } memset(dp, 0, sizeof dp); dp[0][0] = 1; // 第0列没有任何侵入，方案数为1 for (int i = 0; i < m; i++) { // 枚举每一列 for (int j = 0; j < (1 << n); j++) { // 枚举当前列状态 if (dp[i][j] == 0) continue; // 剪枝 for (int k = 0; k < (1 << n); k++) { // 枚举下一列状态 if ((j & k) == 0 && st[j | k]) { dp[i + 1][k] += dp[i][j]; } } } } cout << dp[m][0] << endl; // 第m+1列无侵入，前m列填满 } return 0; }

这段代码有几个细节值得说。第一，dp数组用long long，因为方案数可能很大，N=11, M=11时答案会超过int范围。第二，dp[0][0] = 1是初始状态，表示第0列（虚拟列）没有任何侵入，这是转移的起点。第三，外层循环枚举的是列i从0到m-1，最终答案是dp[m][0]，因为第m列处理完后，第m+1列不应该有任何侵入。

常见坑点：很多人会把dp[0][0] = 1写成dp[1][0] = 1，然后答案输出dp[m+1][0]，这样也能过，但逻辑上不如前者清晰。关键是初始状态和最终答案要对应上，别一个用0-indexed一个用1-indexed，容易搞混。

4. 最短Hamilton路径：集合DP的标准框架

4.1 问题建模与状态设计

最短Hamilton路径的问题是：给定一张n个点的带权无向图，求从起点0到终点n-1，经过每个点恰好一次的最短路径长度。n的范围通常是≤20，因为再大状压就存不下了。

这个题的状态设计非常经典：dp[i][j]表示当前已经走过的点集为i，且最后停在点j的最短路径长度。其中i是一个n位的二进制数，第k位为1表示点k已经走过。

为什么状态要记录“最后停在哪个点”？因为路径的长度和“上一步从哪来”有关。如果我们只知道走过哪些点，不知道当前在哪，就无法计算下一步的边权。所以必须把“当前位置”也纳入状态。

转移的时候，我们枚举“上一个停的点k”，如果k在集合i中且k≠j，那么可以从dp[i - (1<<j)][k]转移过来，加上边权w[k][j]。转移方程：

dp[i][j] = min(dp[i][j], dp[i ^ (1<<j)][k] + w[k][j])

其中i ^ (1<<j)表示从集合i中去掉点j。这个转移的含义是：先走到k，再从k走到j，形成以j结尾的路径。

4.2 转移顺序与边界条件

这个题的转移顺序很关键。我们必须保证在计算dp[i][j]时，所有dp[i ^ (1<<j)][k]都已经计算完毕。由于i ^ (1<<j)一定小于i（去掉一个二进制位，数值必然减小），所以只要按i从小到大枚举，就能保证正确性。

边界条件是dp[1][0] = 0，表示只走过起点0，当前停在0，路径长度为0。其他所有状态初始化为无穷大。

最终答案是dp[(1<<n) - 1][n-1]，即所有点都走过，最后停在n-1的最短路径。

#include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 20, M = 1 << N; int dp[M][N]; int w[N][N]; int main() { int n; cin >> n; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> w[i][j]; memset(dp, 0x3f, sizeof dp); dp[1][0] = 0; // 只走过点0，停在0 for (int i = 1; i < (1 << n); i++) { // 枚举所有集合状态 for (int j = 0; j < n; j++) { // 枚举当前停的点 if (!((i >> j) & 1)) continue; // j必须在集合i中 for (int k = 0; k < n; k++) { // 枚举上一个停的点 if (k == j) continue; if (!((i >> k) & 1)) continue; // k也必须在集合i中 dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][k] + w[k][j]); } } } cout << dp[(1 << n) - 1][n - 1] << endl; return 0; }

4.3 复杂度分析与优化空间

这个写法的复杂度是O(2^n * n^2)。n=20时，2^20约100万，乘以400等于4亿次操作。在C++里如果常数控制得好，勉强能过，但如果时间限制严格（比如1秒），可能需要优化。

优化的方向有几个。第一，把dp数组的第二维用int而不是long long，减少内存访问开销。第二，在内层循环里加剪枝，如果dp[i ^ (1<<j)][k]已经是无穷大就跳过。第三，把w数组用一维或者vector存，提高缓存命中率。

还有一个更本质的优化：我们可以只枚举集合i中为1的位作为k，而不是枚举所有n个点。这样内层循环的次数从n降到popcount(i)，平均能省一半时间。实现方式是用lowbit或者预处理好每个集合的位列表。

// 优化版内层循环：只枚举集合i中的点 for (int i = 1; i < (1 << n); i++) { for (int j = 0; j < n; j++) { if (!((i >> j) & 1)) continue; int prev = i ^ (1 << j); // 枚举prev中的所有点 for (int t = prev; t; t -= t & (-t)) { int k = __builtin_ctz(t); // 获取最低位1的位置 dp[i][j] = min(dp[i][j], dp[prev][k] + w[k][j]); } } }

__builtin_ctz是GCC内置函数，返回一个数二进制中末尾0的个数，也就是最低位1的位置。这个优化在n=20时能把运行时间从4亿次降到大约2亿次，效果还是很明显的。

实操心得：最短Hamilton路径这个题，如果n≤18，朴素写法随便过；n=19或20时，建议加上枚举子集的优化。另外，如果图是稠密图（边权都不大），可以考虑用Floyd预处理最短路，但那样就变成“经过每个点至少一次”了，和原题要求“恰好一次”不同，别搞混。

5. 两个题的对比与状压DP的通用套路

5.1 状态设计的差异与共性

把这两个题放在一起看，会发现它们的状态设计思路有明显差异，但底层逻辑是相通的。

蒙德里安的梦想，状态是“当前列被上一列侵入的情况”，阶段是“列数”。这个状态本质上描述的是边界信息——我们只需要知道上一列对当前列的影响，不需要知道更早的列。这种“只保留必要边界信息”的思想，在轮廓线DP、插头DP里也很常见。

最短Hamilton路径，状态是“已经走过的点集+当前停的点”，阶段隐含在集合大小里。这个状态描述的是完整的决策历史——因为路径长度和所有走过的点都有关，不能只保留边界。

共性在于：两者都用二进制数表示集合，都通过枚举“下一个状态”或“上一个状态”来做转移，都需要保证状态的合法性（蒙德里安要求无奇数连续0，Hamilton要求点必须在集合中）。

5.2 状压DP的通用解题步骤

根据我刷题的经验，状压DP的解题可以总结成四步：

第一步，确定“集合”是什么。是已经走过的点？是当前列被占用的行？是已经放置的棋子？把这个问题想清楚，状态的定义就出来了一半。

第二步，确定“阶段”是什么。阶段可以是列数、行数、集合大小，或者干脆没有显式阶段（直接按集合大小从小到大枚举）。阶段的作用是保证转移的无后效性。

第三步，写出转移方程。问自己：当前状态可以从哪些状态转移来？或者当前状态可以转移到哪些状态？转移的条件是什么？需不需要预处理合法性？

第四步，确定初始状态和最终答案。初始状态通常是“空集”或“只有一个元素的集合”，最终答案是“全集”或“满足特定条件的集合”。

这四步看起来简单，但实际做题时最容易卡在第一步和第三步。我的建议是：先在纸上画几个小规模的例子（比如n=3或n=4），手动模拟一下状态转移的过程，把状态和转移都写清楚，再开始写代码。直接上手写代码很容易写着写着就乱了。

5.3 常见优化技巧汇总

状压DP的优化手段其实不多，但每一个都很实用。我整理了一个表格：

滚动数组这个技巧在蒙德里安的梦想里其实可以用，因为dp[i+1]只依赖dp[i]。但那个题的空间本来就不大（12 * 4096），用不用无所谓。在阶段数很多、状态数很大的题里，滚动数组就是救命稻草了。

6. 实操中容易踩的坑与排查方法

6.1 位运算优先级引发的血案

前面提过一次，这里再强调一遍。C++里位运算的优先级低于比较运算符，所以：

if (s & 1 == 1) // 错误！等价于 s & (1 == 1) = s & 1 if ((s & 1) == 1) // 正确

类似的还有s >> 1 + 1，实际是s >> (1+1)而不是(s >> 1) + 1。我的习惯是：只要涉及位运算和比较、算术混合，一律加括号，宁可多打几个字符也不要留隐患。

6.2 数组越界与状态数计算错误

状压DP的数组大小通常是1 << n，但有时候n=0或者n=1时会有边界问题。比如1 << 0 = 1，数组大小是1，下标只能取0。如果代码里写了dp[1][...]就越界了。

另外，如果n=20，1 << 20 = 1048576，数组开int dp[1<<20][20]就是大约80MB，接近内存限制。这时候要么用滚动数组，要么把第二维压小。我一般会先算一下内存：(1<<n) * n * sizeof(int)，超过256MB就要考虑优化了。

6.3 转移顺序错误导致答案偏大或偏小

最短Hamilton路径里，如果外层循环不是按集合大小从小到大枚举，而是随便枚举，就可能出现“用还没算好的状态去更新其他状态”的情况，导致答案错误。判断方法很简单：如果转移方程里用到了dp[prev][k]，而prev是i去掉一个位，那么prev < i一定成立（二进制数值上），所以按i从小到大枚举是安全的。

蒙德里安的梦想里，外层循环是列数，内层是状态，这个顺序是固定的，不容易错。但要注意dp[0][0] = 1和最终答案dp[m][0]的对应关系，别一个用0一个用m+1。

6.4 常见问题速查表

避坑技巧：写完代码后，先用n=2或n=3的小数据手动跑一遍，把dp数组打印出来，看看每个状态的值是否符合预期。这一步花不了几分钟，但能省下大量调试时间。

7. 从这两个题延伸出去的状压DP变种

蒙德里安的梦想和最短Hamilton路径只是状压DP的起点。实际比赛中，状压DP的变种非常多，但大多数都能从这两个题找到影子。

比如“炮兵阵地”这个题，状态是“当前行的炮兵摆放情况”，但转移时要考虑前两行的状态，所以dp[i][j][k]表示第i行状态为j、第i-1行状态为k的最大炮兵数。这个题的状态合法性判断比蒙德里安复杂得多，需要判断同一行内炮兵是否互相攻击、相邻行是否攻击、隔一行是否攻击。

再比如“玉米田”这个题，和蒙德里安类似，但多了“某些格子不能种”的限制。处理方法是在预处理合法状态时，把和“不能种”的格子冲突的状态也标记为非法。

还有“宝藏”这个题，状态是“已经打通的道路集合”，转移时枚举“从当前集合扩展到新节点”的方案，本质上和最短Hamilton路径的集合DP框架是一样的。

我的建议是：先把蒙德里安和Hamilton这两个题刷熟，理解状态设计和转移的本质，然后再去做变种题。每做一道新题，都问自己：这个题的状态是什么集合？阶段是什么？转移条件是什么？和之前做过的题有什么异同？这样积累下来，状压DP就不再是“靠灵感”的题型，而是有章可循的套路。

最后分享一个我个人的习惯：每次做完一道状压DP，我都会把状态定义、转移方程、边界条件、复杂度分析写在一张卡片上，隔几天再拿出来看一遍。这个方法看起来笨，但对巩固理解非常有效。状压DP的难点从来不是代码本身，而是“为什么这样设计状态”的思维过程。把这个过程想清楚了，代码就是水到渠成的事。