蓝桥杯国赛题解：状态压缩DP在“搭积木”问题中的应用-平芜编程栈

1. 从“搭积木”到“状态压缩”：一道蓝桥杯国赛题的深度拆解

提起“搭积木”，很多人脑海里浮现的是童年时那些色彩斑斓的塑料块。但在2018年蓝桥杯国赛的赛场上，这道名为“搭积木”的题目，却让无数参赛者感受到了从具象到抽象、从直觉到算法的思维跃迁。它不是考你手有多巧，而是考你脑子转得有多快，对计算机状态的理解有多深。我当时在赛场上第一次看到这题，第一反应也是有点懵——积木怎么搭？但静下心来读完题，才发现这其实是一道披着“游戏”外衣的、典型的动态规划与状态压缩结合的经典问题。它考察的核心，远不止是写几行代码，而是如何将现实中的约束（积木的稳定性）转化为计算机可处理的状态模型，并高效地进行状态转移。今天，我就结合当年的解题思路和后续的反复琢磨，把这道题的“里子”和“面子”都掰开揉碎了讲清楚，无论是为了备赛蓝桥杯，还是想深入理解状态压缩DP，这篇文章都能给你带来实实在在的收获。

简单来说，题目给了我们一个宽度为W的“地基”，以及若干块高度为1，但长度（即占据的列数）可能不同的“积木”。积木只能水平放置，不能悬空，且必须保证放置后整体是稳定的（这是关键约束）。我们需要计算的是，在给定的积木集合下，有多少种不同的、稳定的搭法，能够恰好铺满这个宽度为W的地基。这里，“不同”指的是积木的排列顺序不同，或者同一块积木放在不同的位置，都算作不同的方案。这听起来有点像拼图，但加上了“稳定”这个物理条件，难度立刻就上来了。理解并量化这个“稳定”条件，正是解开这道题的第一把钥匙。

2. 问题核心：“稳定”条件的数学化与状态定义

为什么这道题难？难就难在对“稳定”这个感性条件的精确量化。在现实中，一块积木稳定与否，看的是它的重心投影是否落在支撑面内。在本题的简化模型中，我们可以这样理解：地基的每一列都有一个从下往上的“高度”。当我们放置一块长度为L的积木时，它会覆盖连续的L列。这块积木要稳定，就必须满足一个条件：它覆盖的所有列中，当前列的高度必须严格相等。换句话说，积木必须放在一个“平坦”的层面上，不能一头高一头低，否则就会倾斜、不稳定。

举个例子，假设地基宽度W=4，当前各列高度为[0, 1, 1, 0]（表示第1列高度0，第2、3列高度1，第4列高度0）。此时，一块长度为2的积木，可以放在第2、3列（高度都是1），这是稳定的。但不能放在第1、2列（高度0和1不同），也不能放在第3、4列（高度1和0不同）。这就是“稳定”的核心约束。

基于这个理解，整个搭积木的过程，可以看作是从一个初始的“高度轮廓线”开始，不断往上放置积木，从而改变轮廓线的过程。初始轮廓线就是全0（地基）。每放置一块积木，它所在的那几列的高度就会+1。我们的目标，是通过放置若干块（可以重复使用同一种积木）积木，使得最终的轮廓线变成一个平坦的、高度为某个值的平台（因为题目要求恰好铺满，最终所有列高度应该一致，但具体高度值由使用的积木总数决定）。

因此，一个最直接的状态定义呼之欲出：用当前每一列的高度值来表示状态。对于宽度W，状态就是一个包含W个整数的数组。但是，W稍微大一点（比如10），高度的可能取值又很多，这个状态空间就会爆炸，无法遍历。这就是我们需要“状态压缩”的原因。我们并不关心高度的绝对数值，而更关心高度之间的相对关系，特别是“哪里是平坦的、可以放置积木的区间”。

一个经典的压缩技巧是：记录当前轮廓线的“差分”信息，或者更具体地说，关注轮廓线的“上升沿”和“下降沿”。但在这道题里，有一个更巧妙的、与积木放置直接对应的状态表示法：用二进制位来表示当前轮廓线中，哪些位置是“凸起”的，即比它左边的列高。为什么是左边？因为我们在从左到右放置积木时，一个“凸起”标志着一个新区块的开始。更形式化地说，我们定义状态mask为一个W位的二进制数。mask的第i位（从0开始，代表从左数第i+1列）为1，当且仅当第i列的高度大于第i-1列的高度（对于最左边的第0列，我们虚拟一个高度为-1的列，这样第0列永远是一个“凸起”的开始）。为0则表示高度相等或更低（在合法放置中，由于积木必须放在平坦处，不会出现更低的情况，所以通常表示相等）。

这样，一个平坦的区间，就对应着mask中一段连续的0（区间起点是1，后面跟着若干个0，直到下一个1出现）。例如，轮廓线高度[0,0,0,0]对应的mask是1000（假设W=4，仅第0位为1，表示从虚拟列到第0列是上升）。轮廓线[0,1,1,0]对应的mask是1001（第0位1：从虚拟列到第0列上升；第3位1：从第2列高度1到第3列高度0，这在实际中是因为我们放了积木抬高了第2、3列后，第3列右侧是地基，形成了“下降”，但在我们的状态定义中，关注上升沿，这个“下降”实际上意味着下一个平坦区间的开始，所以也记作1）。

这个mask状态巧妙地蕴含了“哪里可以开始放置积木”的信息。一个长度为L的积木，必须放置在一个平坦的区间内。对应到mask上，就是需要找到一个位置i，使得从i开始的连续L位，满足：mask[i]必须是1（区间起点），并且mask[i+1]到mask[i+L-1]都必须为0（区间内部平坦）。放置这块积木后，这个区间的“凸起”标志会被消耗掉，因为放置后这些列的高度被统一加1，原来i位置的“凸起”相对性就消失了。同时，在区间的右端i+L位置，可能会产生一个新的“凸起”（因为右边的列比现在放置的这块积木的顶面低了一截）。因此，状态转移就是从一个mask，通过放置一块积木，转移到另一个mask'。

3. 动态规划递推：状态转移方程的构建与实现

定义了状态mask之后，我们就可以构建动态规划了。设dp[mask]表示当前轮廓线的“凸起”状态为mask时，已经形成的搭积木方案数。初始状态是dp[1 << (W-1)] = 1。这里可能有点反直觉，为什么是1 << (W-1)？根据之前的定义，虚拟一个高度为-1的左边界，那么最左边的第0列肯定是一个凸起（从-1到0）。但在二进制表示里，我们通常把最低位（第0位）代表最左边。一个宽度为W的轮廓线，我们需要W个二进制位。一种常见的处理技巧是，我们使用一个W位的状态，但虚拟一个始终为1的最高位（或最低位，取决于编码习惯）来标记起点。1 << (W-1)就是将最高位（第W-1位）设为1，其余为0，这对应着一个从虚拟左边界开始的、一个贯穿整个宽度的、巨大的“平坦区间”的起点。这个状态代表地基完全平整，尚未放置任何积木，方案数为1。

接下来是状态转移。对于每一个状态mask，我们尝试所有可能的积木放置位置和所有类型的积木。对于一块长度为L的积木，我们需要遍历所有起始位置i(0 <= i <= W-L)，检查是否满足放置条件：

mask的第i位必须是1（区间起点）。
mask的第i+1位到第i+L-1位必须都是0（区间内平坦）。

如果满足，则可以进行放置。放置后，新的状态new_mask如何计算？

首先，将原mask的第i位清零（消耗掉这个起点）。
然后，将原mask的第i+L位（如果i+L < W）置为1。这是因为放置积木后，积木的右边缘形成了一个新的“台阶”，相对于积木顶面，右边的列变低了，因此从积木顶面到右边列，形成了一个新的上升沿（即新的凸起起点）。这是整个状态转移中最关键也最容易出错的一步，需要仔细理解其物理意义：我们放置的积木创造了一个新的、高度更高的平面，这个平面的右边界，就是下一个潜在平坦区间的左边界。
注意，在i+1到i+L-1这些位置，原状态已经是0，放置后它们被积木覆盖，高度统一增加，它们之间的相对高度差仍然是0，所以在新状态中仍然保持为0。
原mask中其他位的值（除了i和i+L）直接保留到new_mask。

用位运算可以优雅地实现：

// 假设 mask 是当前状态，L是积木长度，i是起始位置（0-index） if ( (mask & (1 << i)) && ((mask & (((1 << L) - 1) << i)) == (1 << i)) ) { // 条件判断：第i位为1，且从i开始的L位中，只有第i位是1，其余L-1位都是0 int new_mask = mask; new_mask &= ~(1 << i); // 清除第i位 if (i + L < W) { new_mask |= (1 << (i + L)); // 设置第i+L位 } // 注意：还需要处理原mask中可能被“覆盖”掉的位，但因为我们只检查了相关位为0，所以直接清除和设置即可。 // 更严谨的做法是：new_mask = (mask & ~(1<<i)) | ((i+L<W) ? (1<<(i+L)) : 0); // 但前提是确保(mask & (((1<<L)-1) << i)) == (1<<i)成立，这意味着中间位全0。 dp[new_mask] += dp[mask]; }

这里((1 << L) - 1) << i生成了一个从第i位开始的、连续L位为1的掩码。(mask & ...) == (1 << i)就确保了在这L位中，只有第i位是1，其他位都是0。

最终，我们关心的答案是什么？是所有积木恰好铺满地基的方案数。在我们的状态模型中，“铺满”意味着整个轮廓线达到了一个统一的高度，并且没有未结束的“凸起”。这对应着最终状态mask为0。因为如果所有列高度一致，那么没有任何一列比它左边的列高，所以mask的所有位都应该是0（除了我们虚拟的起点，但那个起点在状态转移中已经被消耗掉了）。因此，答案就是dp[0]。

然而，这里有一个巨大的陷阱，也是当年很多选手折戟的地方：积木是可以重复使用的。题目并没有说每种积木只能用一次。这意味着我们的DP转移不能简单地按积木顺序进行，而必须处理“无限背包”问题。上面的转移方程dp[new_mask] += dp[mask]是一种“我为人人”的递推，如果放在循环里，一块积木可以被使用多次。但这样直接写会导致重复计算和顺序问题。更标准的方法是采用记忆化搜索（DFS+Memoization）或者按状态刷表的DP，并在转移时，认为积木是无限的，每次都可以使用任何积木。

一个标准的实现框架是：

预处理出所有积木的长度列表blocks。
定义记忆化数组memo[mask]，表示从状态mask出发，铺满剩余区域（即到达状态0）的方案数。
编写递归函数dfs(mask)：
- 如果mask == 0，返回1（已经铺满）。
- 如果memo[mask]已计算，直接返回。
- 否则，初始化方案数res = 0。
- 遍历每一块积木长度L。
- 遍历每一个可能的起始位置i。
- 检查在mask状态下，能否在位置i放置长度为L的积木。
- 如果能，计算出新状态new_mask，然后res += dfs(new_mask)。
- 将结果存入memo[mask]并返回。
初始调用dfs(init_mask)，其中init_mask是初始状态（如1 << (W-1)）。

这种记忆化搜索的好处是逻辑清晰，天然避免了重复计算的复杂性，并且直接给出了从初始状态到结束状态的总方案数。

4. 算法优化与细节处理：位运算技巧与去重

虽然记忆化搜索的思路很直接，但当W较大（比如10以上）时，状态总数是2^W，对于每个状态，我们需要遍历所有积木（假设M种）和所有可能的位置（W个），那么最坏复杂度是O(2^W * M * W)。对于W=10，2^10=1024，这个计算量是可以接受的。但如果W更大，或者积木种类很多，就需要优化。

优化点一：预处理可放置位置。对于每一个状态mask，我们不需要每次都遍历所有i和L来检查是否可放置。我们可以预处理出，对于一个给定的mask，所有可能的(i, L)对。具体来说，我们可以遍历mask中所有为1的位i（这些是潜在的区间起点），然后对于每个起点i，向右扩展，看连续0的个数有多少（即平坦区间的长度）。假设从i开始，连续有k个0（直到下一个1或者边界），那么长度从1到k的积木都可以放在这里（因为需要L-1个连续的0）。这样，我们只需要遍历状态中为1的位，然后向右扫描，就能得到所有合法的放置方式，避免了无效的i和L组合的遍历。

优化点二：状态编码与哈希。mask是一个W位的二进制数，可以直接用整数表示，作为数组下标。这是状态压缩DP最方便的地方。记忆化数组memo的大小就是1 << W。

关键细节：去重。这是本题另一个极其容易出错的地方。题目要求计算“不同的搭法”。如果积木长度有重复，比如有两块长度相同的积木，那么在使用记忆化搜索时，直接遍历积木列表，就会把“先放A再放B”和“先放B再放A”当成两种不同的方案，但实际上，因为积木是完全相同的，这两种顺序应该被视为同一种方案。这就是“顺序”导致的重复计数。

如何解决？我们不是在放置“具体的某一块”积木，而是在选择“一种长度”的积木。因此，我们应该对积木长度列表进行去重和计数。假设长度L有cnt[L]块。那么，在状态转移时，我们不再遍历积木列表，而是遍历所有不同的长度L。但是，这还不够。即使长度相同，一次放置一块和一次放置两块，也是不同的操作。我们需要考虑的是：在当前状态下，我们可以选择放置k块长度为L的积木（k从1到cnt[L]），只要位置允许。但这样组合情况会非常复杂。

一个更精妙且正确的思路是：将问题转化为完全背包问题。我们把“放置一块长度为L的积木”看作一种“操作”，这种操作会将状态从mask转移到new_mask。不同的长度L对应不同的操作。现在，我们有无限次这样的操作（因为每种长度的积木有足够多的数量，题目通常理解为无限，或者至少足够铺满）。我们要计算的是，使用这些操作，从初始状态init_mask走到最终状态0的操作序列有多少种。注意，这里“操作序列”的不同，在于每次选择的“操作”（即放置哪种长度的积木在哪个位置）不同。即使长度相同，放在不同位置，也是不同的操作。

因此，重复的积木长度不会导致重复计数问题。因为当我们有两种长度相同的积木时，在“操作”层面，它们被视为同一种“操作类型”（长度为L的放置操作）。我们计算的是不同操作序列的数量，而不是区分物理上哪块积木。所以，我们只需要对积木长度列表去重，然后用去重后的长度集合来进行状态转移即可。在记忆化搜索中，我们遍历所有不同的长度L，对于每个L，再遍历所有能放置它的位置i。这样计算出来的方案数，自动就是题目要求的“不同搭法”的数量。

注意：这一点需要仔细品味。很多人在此纠结于组合数学的重复计数，实际上题目中“不同的积木”如果长度相同，在计算方案数时，只要它们被放置的位置序列不同，就算不同方案。我们算法中生成的所有合法操作序列，已经一一对应了这些不同的方案。去重长度只是为了不重复计算相同的操作类型。

5. 代码实现与实战演示：从理论到AC

理论分析完毕，我们来看一个针对典型数据规模的C++实现。假设宽度W不超过10，积木种类数M不超过10。

#include <iostream> #include <vector> #include <cstring> #include <algorithm> using namespace std; int W; // 地基宽度 vector<int> blocks; // 积木长度列表（已去重） long long memo[1 << 10]; // 记忆化数组，W最大10，所以状态数最多2^10=1024 // 检查在状态mask下，能否从位置pos开始放置长度为len的积木 bool canPlace(int mask, int pos, int len) { // 1. 起始位必须是1 if (!(mask & (1 << pos))) return false; // 2. 从pos+1开始的len-1位必须都是0 int area = ((1 << len) - 1) << pos; // 生成[pos, pos+len-1]区间的掩码 // 我们期望的是：只有pos位是1，其他位是0 return (mask & area) == (1 << pos); } // 计算放置后的新状态 int placeBlock(int mask, int pos, int len) { int new_mask = mask; // 清除起始位的1 new_mask &= ~(1 << pos); // 在结束位置设置新的1（如果没超出右边界） if (pos + len < W) { new_mask |= (1 << (pos + len)); } // 注意：原区间[pos+1, pos+len-1]的位本来就是0，保持不变 return new_mask; } // 记忆化搜索 long long dfs(int mask) { if (mask == 0) return 1; // 铺满，找到一种方案 if (memo[mask] != -1) return memo[mask]; long long res = 0; // 遍历所有不同的积木长度 for (int len : blocks) { // 遍历所有可能的起始位置 for (int i = 0; i <= W - len; ++i) { if (canPlace(mask, i, len)) { int new_mask = placeBlock(mask, i, len); res += dfs(new_mask); } } } return memo[mask] = res; } int main() { // 假设输入：第一行W和M，第二行M个积木长度 int M; cin >> W >> M; vector<int> raw_blocks(M); for (int i = 0; i < M; ++i) { cin >> raw_blocks[i]; } // 对积木长度去重 sort(raw_blocks.begin(), raw_blocks.end()); blocks.erase(unique(blocks.begin(), blocks.end()), blocks.end()); // 初始化记忆化数组 memset(memo, -1, sizeof(memo)); // 初始状态：最高位（第W-1位）设为1，代表最左边的起点 int init_mask = 1 << (W - 1); long long ans = dfs(init_mask); cout << ans << endl; return 0; }

代码要点解析：

canPlace函数严格实现了我们之前推导的放置条件检查。
placeBlock函数实现了状态转移的核心位运算。
dfs函数是标准的记忆化搜索模板。注意递归基是mask == 0。
在主函数中，我们对输入的积木长度进行了去重，这是为了避免对同一种操作类型的重复遍历，是正确性的关键一步。
初始状态init_mask设置为1 << (W-1)。这里将“起点”标志放在了最高位。你也可以选择放在最低位，但相应的位运算需要调整。关键是保持定义一致。

复杂度分析：状态数S = 2^W。对于每个状态，我们需要检查所有长度L（去重后假设为U种）和所有起始位置i（最多W个）。最坏情况下，每个状态的计算复杂度是O(U * W)。因此总时间复杂度为O(S * U * W)。在W=10, U<=10时，计算量大约在10^5量级，完全可以在1秒内完成。

6. 常见错误与调试技巧：避开那些年我们踩过的坑

这道题在实现时，有几个坑点一不留神就会掉进去，我结合自己调试的经验和大家分享一下。

坑点一：初始状态设置错误。这是最致命的错误之一。为什么是1 << (W-1)？我们再来理解一下：我们的状态mask表示“凸起”的位置。在没有任何积木时，整个地基是平的。从左边界（虚拟列，高度-1）到第0列（高度0），这是一个“上升”，所以第0位应该为1。如果我们用W位二进制数，最低位（第0位）代表最左边，那么初始状态应该是1（二进制00...001）。但在很多参考代码中，为了处理方便，他们使用1 << (W-1)，这实际上是把最高位当作最左边。这两种定义都是可以的，只要你在状态转移时保持一致。我建议在纸上画一个W=3的小例子，分别用两种初始状态推演一下，看最终dp[0]是否一致。关键是要理解其物理意义，并确保canPlace和placeBlock函数与你的状态定义匹配。

坑点二：状态转移时，新凸起位置设置错误。在placeBlock函数中，new_mask |= (1 << (pos + len))这一行，条件必须是pos + len < W。如果pos+len == W，说明积木正好放到了最右边，此时右边没有列了，因此不会产生新的凸起。如果错误地设置了这一位，会导致状态空间错乱，答案通常是0或者荒谬的大数。

坑点三：重复积木长度处理不当。正如第四节详细讨论的，如果不对长度去重，直接遍历原始积木列表，当有相同长度的积木时，会导致方案数多算。因为算法会认为“放置第一块长度为L的积木在位置A”和“放置第二块长度为L的积木在位置A”是两个不同的操作，从而生成两条本质上相同的路径（因为积木不可区分）。去重是必须的。

坑点四：递归深度与栈溢出。虽然W<=10时状态数不多，但递归深度可能达到放置积木的最大数量，理论上可能很深。不过在实际数据中，这个深度是有限的。如果担心栈溢出，可以采用迭代的动态规划，即刷表法。用dp[state]表示到达该状态的方案数，初始dp[init_mask]=1，然后遍历所有状态s，对于每个s，遍历所有可执行的操作（长度L和位置i），更新dp[new_state] += dp[s]。最终答案仍是dp[0]。这种方法避免了递归，但需要保证状态转移顺序，通常按状态值从小到大遍历即可。

调试技巧：

小数据暴力对拍：写一个暴力DFS枚举所有放置顺序的程序（适用于W和积木数非常小的情况），与你的状态压缩DP程序对比结果。这是最可靠的调试方法。
打印状态转移图：对于W=3或4的情况，手动计算所有状态，并打印出你的程序计算出的dp值或dfs返回值，与手动计算的结果对比。
关注边界：特别注意积木放在最左边(i=0)和最右边(i=W-L)的情况，检查canPlace和placeBlock的逻辑是否正确。
使用long long：方案数可能非常大，远超int范围，务必使用long long来存储方案数。

7. 举一反三：状态压缩DP的思维模式与变种

解完这道题，我们收获的不仅仅是一道题的答案，更是一种重要的算法思维模式——状态压缩动态规划。其核心在于：将一组具有多个维度、但每个维度状态数有限的信息，压缩成一个整数（通常是二进制数）来表示。关键在于找到一种压缩方式，使得状态之间的转移可以高效计算。

“搭积木”这道题的状态定义（用“凸起”位表示轮廓线）非常经典，它实际上是轮廓线DP的一种特殊形式。轮廓线DP常用于解决网格铺放问题（如铺瓷砖、棋盘覆盖）。这类问题的共性是需要记录当前处理位置的“轮廓线”信息，而“搭积木”可以看作是一维的轮廓线问题。

我们可以思考几个变种：

积木有高度：如果积木不是高度为1，而是有不同高度，那么状态就不能只用“凸起”表示了，可能需要记录每个列的绝对高度，或者高度差。状态复杂度会急剧上升。
地基有初始高度：如果地基不是平的，而是有一个初始的轮廓线。那么我们初始的mask状态就需要根据这个初始轮廓线来计算，而不是简单的1 << (W-1)。计算方法是：遍历每一列，如果当前列高度大于前一列高度，则对应位设为1。
求最大高度或最小积木数：问题可能不是求方案数，而是求能搭到的最大高度，或者用给定积木铺满地基所需的最少积木数。这时，我们的DP值就需要从方案数改为最大高度或最小数量，状态转移方程也要相应调整。
二维搭积木：这才是更一般的轮廓线DP问题。例如在一个网格上放置不同形状的积木，状态需要压缩当前行的轮廓信息（通常用插头DP或基于行的轮廓线DP），难度会大大增加。

理解了一维的“凸起”状态表示法，就为学习更复杂的轮廓线DP打下了坚实的基础。其精髓在于，我们只关心那些影响后续决策的“关键特征”（在这里就是平坦区间的起点），而忽略了那些无关紧要的细节（高度的具体数值）。这种抓主要矛盾的抽象能力，是解决复杂算法问题的关键。

最后，回顾这道“搭积木”，它之所以能成为蓝桥杯国赛的经典题目，正是因为它完美地融合了算法思维（动态规划、状态压缩）、问题建模（将物理稳定条件转化为数学约束）和编程实现（位运算技巧）。通过这道题，我们不仅学会了一个算法，更学会了一种如何思考复杂问题的方法——先深入理解约束，再寻找关键特征，最后设计高效的状态表示与转移。这才是竞赛和实际工程中，最值得我们锤炼的核心能力。