企业官网建设流程全解析

还没有主标题，直接以二级标题开头。这题是CSES题库里Dynamic Programming章节的一道经典题，也是状态压缩DP入门必刷的题目。我先说结论：这道题的核心是“以电梯趟数为目标，用位掩码表示乘客集合，通过DP求最少趟数”，适合刚学完基础DP、想接触状态压缩的算法竞赛选手，也适合准备面试时想复习位运算DP的人。

1. 题目拆解与数据规模分析

1.1 题面背后的真实含义

“Elevator Rides”题面很短：n个人要坐电梯上楼，电梯限重x，每个人体重已知，问最少要几趟才能把所有人送到。

这个场景在我们生活中很常见，但放到算法题里，恶心的地方在于：电梯容量不只看人数，还看总重量。也就是说，每一趟能装哪几个人，取决于这一组的体重之和不能超过x，至于装几个人没有上限。只要一组人的体重总和在限重以内，这一趟就是合法的。

我当初第一次读题时，第一反应是“这不就是背包吗”，但仔细想并不是。背包问题的目标是最大化装载价值，而这里的目标是最小化趟数，且每个人必须被分配且只能分配到一个组里，本质上是一个集合划分问题。

1.2 为什么 n ≤ 20 是解题的金钥匙

题目给的数据范围是n ≤ 20，这个数字不是随便定的。20个人，如果让我用朴素的方式枚举所有分组方案，这属于Bell数的范畴，爆炸得没法看。但20恰好适合用位掩码表示：一个int整数，用二进制位表示每个人是否已被装载，1表示已装，0表示未装，总状态数就是2^n = 1,048,576。这个数量级对现代计算机来说非常友好，内存和时间都扛得住。

这就是状态压缩DP（bitmask DP）的经典适用场景：集合大小在20左右，需要用集合的子集作为状态。拿到题第一件事，不要急着写代码，先看数据范围，n ≤ 20基本就是在明示“用状压DP”。

我再说一个更具体的判断依据：如果n ≤ 12，那DFS加剪枝可能也能过；但n = 20时，普通搜索会超时，而2^20约一百万，配上O(n·2^n)的转移，总计算量约两千万次，完全在1秒时限内。数据范围就是出题人留给你的解题信号，错过这个信息，后面所有设计都会跑偏。

1.3 一个容易踩的直觉误区

很多人（包括我）看到“最少趟数”这四个字，会直觉地想：是不是把所有人按体重排序，然后从重到轻贪心地塞进当前这趟电梯？

我拿一个例子说明这为什么是错的。比如电梯限重10，四个人体重分别是6、5、5、4。排序后贪心：第一趟放6，剩下4放不下（6+4=10），于是6单独一趟；然后5、5一趟超重，所以5单独一趟，另一个5单独一趟，最后4凑进第一趟或自己一趟，总共3趟甚至4趟。但最优方案是6+4一趟，5+5一趟，总共2趟。贪心只看当前局部最优，无法处理这种跨趟的组合权衡，所以必须用DP来全局决策。

理解了这一步，就明白为什么状压DP是正解了：我们需要枚举所有可能的分组，并在分组之间找到最优的拼接方案。

2. 状态定义与DP转移设计

2.1 两个数组：最少趟数 + 最后一趟剩余容量

这道题最经典的状压DP写法，是用两个数组配合转移。

• dp[mask]：表示已经装载了mask这个集合的人，所需要的最少趟数。
• last[mask]：表示在达到dp[mask]这个最优趟数时，最后一趟电梯的剩余载重量（或者说已用重量）。

为什么需要两个数组？因为如果只记录趟数，我们无法知道当前最后一趟还剩多少空间，也就不知道下一趟还能不能塞进新的人。dp数组管目标，last数组管约束，二者缺一不可，这是这道题最核心的设计点。

状态转移的思路是这样的：假设当前集合是mask，里面已有若干人。我们想再加入一个人i（前提是i不在mask中），形成新集合mask2 = mask | (1 << i)。如果last[mask] >= weight[i]，说明当前这趟还能装下i，那么dp[mask2] = min(dp[mask2], dp[mask])，last[mask2] = max(last[mask2], last[mask] - weight[i])；如果装不下，则必须新开一趟，dp[mask2] = min(dp[mask2], dp[mask] + 1)，last[mask2] = max(last[mask2], x - weight[i])。

这里有个细节要注意：dp[mask2]可能从不同的mask转移过来，每种转移对应的last[mask2]不同，而last数组存的应该是“在dp值最优时的最大剩余容量”。所以当dp值相同时，我们倾向于保留last更大的方案，因为剩余空间越大，后面越有可能往这趟里继续加人，这对减少趟数是有利的。

2.2 初始状态与枚举顺序

初始状态是空集mask = 0，此时dp[0] = 0，last[0] = x（电梯空着，剩余容量就是限重）。

枚举顺序上，我习惯从小到大枚举mask，从0遍历到(1 << n) - 1，保证每个mask在处理之前，它的所有子状态已经处理完毕。因为我们的转移总是从较小的集合走向较大的集合（加入一个人），所以按mask数值递增枚举是可行的，这也是位运算DP最常见的遍历方式。

有人会问：dp[mask]中某一趟装的人是不是有顺序要求？在同一个mask里，人的顺序并不重要，因为mask只表示“集合里有谁”，不表示“谁先谁后”。这种天然的无序性正是集合划分类DP的优点：我们不需要关心分组内部的排列，只需要关心分组之间的拼接。

2.3 为什么要在dp值相同时保留更大的last

再深入说下这个点。假设dp[mask2]当前已经被赋值为3，此时last[mask2] = 2。后来另一个状态转移过来，发现dp[mask2]还是3，但这个新方案last[mask2] = 5。这个时候必须更新last[mask2] = 5。

原因很简单：同样都是3趟，最后一趟剩余5肯定比剩余2更能容纳后续的乘客。比如后面还剩个体重为3的人，剩余2的方案装不下，剩余5的方案就能直接塞进最后一趟，不会增加总趟数。这个更新策略实际上是一种贪心思想：在dp值相同的情况下，保留未来扩展能力更大的状态。

这一步写不好，最容易出现的问题是：dp[mask2]已经是最小值，但你忘记把last更新成更大的值，导致后续转移时错误地多开了新的一趟，最终答案偏大。这种bug在本地样例上可能测不出来，但在大数据量下会出问题，我当初在这上面卡了很久。

2.4 后续可以如何优化

基础写法的时间复杂度是O(n·2^n)，因为每个mask都要尝试加入n个人。在n=20时约两千万次运算，已经足够快。但如果追求更优的写法，可以预先枚举所有“合法趟次”（即体重和不超过x的子集），再对这些子集做DP，但那样复杂度反而变成O(3^n)，在n较大时反而更差。

所以这个基础写法其实是时间复杂度和实现难度都很均衡的解法。我后面在“常见问题”里还会提到一种递归枚举子集的替代思路，但结论是：就这道题的数据范围而言，O(n·2^n)的写法就是最优解。

3. 核心代码实现与关键细节

3.1 我的C++17实现

直接贴我当时AC的代码，并在后面逐段解释：

#include <bits/stdc++.h> using namespace std; const int INF = 1e9; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, x; cin >> n >> x; vector<int> w(n); for (int i = 0; i < n; i++) cin >> w[i]; int total = 1 << n; vector<int> dp(total, INF); vector<int> last(total, -1); dp[0] = 0; last[0] = x; for (int mask = 0; mask < total; mask++) { if (dp[mask] == INF) continue; for (int i = 0; i < n; i++) { if (mask & (1 << i)) continue; int nmask = mask | (1 << i); if (last[mask] >= w[i]) { int cand = dp[mask]; int nlast = last[mask] - w[i]; if (cand < dp[nmask] || (cand == dp[nmask] && nlast > last[nmask])) { dp[nmask] = cand; last[nmask] = nlast; } } else { int cand = dp[mask] + 1; int nlast = x - w[i]; if (cand < dp[nmask] || (cand == dp[nmask] && nlast > last[nmask])) { dp[nmask] = cand; last[nmask] = nlast; } } } } cout << dp[total - 1] << endl; return 0; }

这段代码的核心逻辑我拆成三层说：外层循环负责遍历所有mask，内层循环负责尝试加入一个新的乘客。每次加入时先判断当前这一趟（即mask对应的最后一趟电梯）是否还有足够的剩余容量，能装下就复用当前趟，不能装下就开一趟新的。

3.2 为什么需要if (dp[mask] == INF) continue;

这个判断很多人会忽略，但它是正确性和性能的双重保障。从正确性上讲，如果一个mask永远无法到达（理论上不会发生，因为任何非空集合都可以通过逐步加入变成），跳过它可以防止用无意义的状态污染后续转移。从性能上讲，n=20时有一百万个mask，虽然大部分都能到达，但这一行判断的开销几乎为零，省去了无谓的计算。

更关键的是，如果不加这个判断，last[mask]为-1时，last[mask] >= w[i]这个条件可能出现误判，导致状态错误。加了判断之后，我们只从合法状态出发，整个DP图是干净的。

3.3 更新条件里为什么要写|| (cand == dp[nmask] && nlast > last[nmask])

我见过不少初学者直接写成：

if (cand < dp[nmask]) { dp[nmask] = cand; last[nmask] = nlast; }

这种做法在dp值不同时没问题，但当cand == dp[nmask]时，它不会更新last。前面已经强调过，相同趟数下剩余容量更大的状态更优。如果不做这个额外判断，可能错过容量更大的状态，最终的趟数可能不是全局最优。

举个实际例子：n=3，x=10，体重分别为5、5、6。从空集出发，第一种方式先加入5再加入5，两趟之后得到dp = 1，last = 0；第二种方式先加入6再加入5，同样dp = 2（6单独一趟，5单独一趟），last = 5？其实这里发展不直观，但核心意思是：相同趟数下last更大的方案，在后续转移中有可能直接把第三个人加进最后一趟而不增加趟数。跳过last更新，就会在隐藏用例中出错。

3.4 另一种写法：二分查找优化趟次上限

我还看到过不少AC代码用二分答案的思路，把问题转化为“验证是否可以m趟装完”，然后配合DFS或DP判断可行性。这个方向也能过，但要写DFS剪枝，实现复杂度明显更高，而且状态设计容易跟位运算纠缠在一起，对新手不友好。

我个人推荐直接用上面的O(n·2^n)写法，思路直观，代码量小。当你把dp和last两个数组的含义吃透后，再遇到“最少分组”“最少装箱”类题目，可以直接把这个模板迁移过去。

4. 常见问题与调试技巧实录

4.1 问题一：答案偏大，且小数据正常、大数据出错

这个症状几乎可以断定是last更新策略不对。我调试时用了一个很笨但很有效的方法：写一个暴力DFS枚举所有分组方案来对拍，生成n=10以内的随机数据，对比DP结果。如果小数据对拍通过，但放到n=15、n=20数据上出错，重点检查“相同dp值时是否更新last为更大值”。

排查时还可以打印中间状态，看dp数组中每个mask对应的last值是否合理。比如dp[mask] = 3时，last[mask]应该小于等于x，如果出现负数或者超过x，说明转移时的重量处理有误。

4.2 问题二：位运算优先级导致编译错误或逻辑错误

mask & (1 << i)的判断，如果写成mask & 1 << i，在C++里其实是(mask & 1) << i，因为移位运算符优先级高于按位与。虽然这里判断结果是0或非0，单纯逻辑上可能碰巧没错，但写代码时最好加上括号，明确意图，节省自己和他人的理解成本。

如果你用Python写，要注意Python的无限精度整数不会溢出，但1 << n当n=20时没问题，n超过30时for循环会退化到不可接受，不过这道题n=20，Python也完全能跑。

4.3 问题三：dp数组的初始值设置

我把dp初始化为INF时用的是1e9，这个值足够大，远大于n的最大值20，确保不会在min比较时被误覆盖。有些代码用INT_MAX，其实也可以，但INF + 1可能溢出成负数，比较时会出大问题。稳妥起见用1e9这类安全的大数就好。

last数组我初始化为-1，这是故意的。因为空集是唯一合法的出发点，其余状态的last在未更新前为-1，恰好作为“无效状态”的标记。配合if (dp[mask] == INF) continue;，不会出现误用-1去转移的情况。

4.4 调试技巧总结

• 对拍是最高效的调试手段。写一个DFS枚举所有分组方案的暴力程序，n不超过10时和DP结果对拍。
• 打印每个mask的dp和last值，从0开始逐步验证，特别关注加入一个人时是复用电梯还是开新电梯的分支。
• 测试边界：n=1时，答案一定是1；所有人体重之和不超过x时，答案一定是1；单人体重就超过x的情况题目通常不会给，但程序也应能正确处理（实际上如果存在个体重大于x，DP会自动让该人独自一趟，然后发现趟数大于等于人的数量，此时注意输出dp[total-1]仍能正确反映趟数）。

注意：如果测试数据里出现某个人的体重单独大于限重，这在物理上不可能坐同一部电梯，题目通常保证数据合法。若遇到异常数据，建议检查体重范围，不要盲目修改算法。

4.5 关于时间的进一步优化

前面说过O(n·2^n)对n=20足够快。但如果你希望追求极限，还可以做一个小优化：在循环内提前计算好每个mask对应的“最优单人候补列表”。比如用lowbit技巧，只尝试加入mask中尚未加入的人里编号最小的若干个，其实无法从渐近意义上改变复杂度，但对常数有一定优化。

实践中我还试过用Python写的版本，因为Python的位运算和列表操作在n=20时依然可以接受，大概0.3秒左右能跑完。C++版本则基本是秒过。如果你在AtCoder等平台上交Python，记得用sys.stdin.readline加速输入，避免IO成为瓶颈。

5. 针对这道题的思考角度与扩展

5.1 换个角度看问题：分组最小化

这道题的本质是：把集合S划分为若干个子集S1, S2, ..., Sk，每个子集的和不超过x，求k的最小值。这种“最小划分数”模型在整个动态规划里非常常见。

类似的模型可以迁移到这些场景：把一堆任务分成若干批，每批有资源上限，求最少批数；把n个物品装进容量为x的箱子，求最少箱子数；甚至可以把“电梯趟数”替换成“服务器批次”“日程天数”等现实概念，DP结构不变。

掌握了这道题，再看到“n个人分成若干组，每组满足某个约束，求最少组数”这类问题时，心里就应该立刻浮现出bitmask DP的框架：用mask表示人的集合，dp记录最少组数，额外的数组记录“当前最后一组剩余的容量/剩余额度”。

5.2 和背包问题的对比

很多人觉得这题像背包，我专门说说区别。背包问题的每个物品有一个价值和一个重量，要在容量限制下最大化价值，物品之间没有“只能分一次”的集合约束。而这题里的人必须属于且仅属于一趟，我们要做的是集合划分，不是选择装载。

这个区别决定了状态设计的不同：背包用一维容量数组滚动更新，这题需要用mask表示已经装的人。如果强行用背包思路解，你无法处理“哪些人已经分配过”这个状态，就会漏解。意识到这一点，是理解这题的关键一步。

5.3 后续可以尝试哪些进阶题目

刷完这道题，建议按这个顺序巩固：

1. CSES里的“Meet in the Middle”相关题目，练习集合折半枚举的思路。
2. “Minimum XOR Sum of Pairs”这类用位掩码DP处理配对的题目。
3. 带权二分匹配（Kuhn-Munkres）前可以先做几道bitmask DP热身，因为二分匹配的DP版本也是mask思想。

这些题目看似各不相同，但底层的“用mask表示集合+dp值表示最优解”是个通用框架。把Elevator Rides吃透，后面很多东西会顺畅很多。

5.4 什么时候不该用状压DP

最后说点忠告：状压DP不是万能的。如果n超过25，2^n的状态数就超过三千万，内存和时间都开始吃紧；如果n超过30，基本可以放弃状压。这时候要想想题目是否有贪心性质、是否可以用二分图匹配、是否可以用网络流来表达。

判断标准很简单：数据范围n≤20且问题是集合划分类，优先考虑状压DP；数据范围一大，先找找有没有更本质的规律。算法题最怕的不是不会做，而是用了错误级别的方法去硬套，最后时间超限还不知道原因。

我在实际训练中还有一个体会：这道题的dp + last双数组写法，几乎可以直接套用到“最少卡车运输”的题目上，只需要把“电梯限重”换成“卡车载重”，把“体重”换成“货物重量”，代码一个字不用改就能AC。这种一鱼多吃的收获感，是我刷题时最看重的。