1. 题目拆解电梯载人问题的真正考点先说说这道题是什么。CSES题单里的“Elevator Rides”表面上看是个电梯调度问题本质上考的是状态压缩DP。原题大意是有n个人要坐电梯上楼每个人有体重上限电梯载重上限是x问最少需要跑几趟才能把所有人送上去。n的上限给得很微妙只有20。见过这类题的老手一看这个n就知道八成是2^n级别的状态压缩过不去但20恰好是位运算状态DP的舒适区。不少朋友第一次做这道题时会觉得“这不就是个贪心嘛按体重从大到小排能塞就塞”。真这么做前面几组样例可能能过但往深处测就崩了。举个反例电梯载重10四个人体重分别是6、6、5、5。按贪心65一趟另一组65又是一趟刚好两趟。但如果是65、56之外的组合比如66一趟放不下那不就麻烦了这个反例还不算狠真正的问题在于贪心策略无法穷举“哪几个人坐同一趟”这个组合层面的决策空间。所以这道题的正确解法不是贪心是DP。核心考点有三层组合优化目标函数是最小化“趟数”这是个典型的划分问题要把n个人分成若干子集每个子集的体重和不超过x求最小子集数。状态压缩n≤202^20约等于100万枚举所有子集可行。DP状态设计用两个数组分别记录“当前趟数”和“当前趟剩余载重”状态转移时用位运算枚举“未上电梯的人”作为新加入集合的候选。理解了这三个考点题目就不难了。但难的地方在DP状态转移的写法和边界控制这才是真正区分新手和老手的分水岭。下面一点一点拆。2. 状态设计用两组数组承载“最少趟数”和“剩余空间”两个信息2.1 为什么单用一个dp数组不够我一开始接触这道题的时候很自然地想用一个一维数组dp[mask]表示“当前已经带上电梯的人集合是mask时的最少趟数”。逻辑听起来顺但真写起来会卡住假设dp[mask]3但最后一趟已经装了60kg而另一组dp[mask]同样等于3但最后一趟只装了20kg。这两个状态虽然趟数一样但“继续装新人的能力”完全不同。电梯剩余重量决定了后续还能不能往当前这一趟里加人。如果不记录剩余载重那么状态转移的时候就不知道新乘客应该“塞进现有这一趟”还是“新开一趟”。所以正解是开两个数组同步更新dp[mask]当前mask状态所需的最少趟数。last[mask]达到dp[mask]趟数时最后一趟已经占用的重量。这样在设计状态转移时如果新加入的人还能放进当前这一趟趟数不变last更新如果放不下趟数加一新的一趟只装这个人。用生活化类比就是你手里有一排箱子每个箱子有承重上限。你现在要把几件物品装箱想知道最少要用几个箱子。只记“用了几个箱子”不够你还得知道“最后一个箱子还剩多少空间”不然下一件物品不知道该塞哪一个可能塞得下也可能必须开新箱子。两个信息缺一不可。2.2 状态转移的完整过程假设当前已经处理完mask集合最后一趟剩余空间是x - last[mask]。现在想加入一个不在mask里的人i体重是w[i]。分两种情况如果w[i] ≤ x - last[mask]说明可以塞进当前最后一趟。此时dp不变last更新为last[mask] w[i]。如果塞不下则必须新开一趟。dp加1last更新为w[i]。然后对所有不在mask里的i做一遍尝试取最小dp的转移结果。如果有多个选择都能把趟数降到最低那last应该取“最后一趟占用重量最小”的那个因为剩余空间越大对未来转移越有利。这里有个关键优化状态转移时不能只拿“第一个可行的i”就完事因为对同一个mask不同的转移来源会生成不同的last即便dp值相同last越小越优。一个比较好的写法是在遍历mask的所有超集或通过添加单个人生成新状态时用“能小就小”的原则更新last。比如从某个状态premask添加人i到mask比较dp[premask]新开趟数是否比当前dp[mask]小或者相等但last更小就更新。2.3 为什么这种“趟数优先、last次之”的序关系是对的这本质上是一个多目标优化下的贪心选择。因为dp和last是两个数值一个代表已用趟数一个代表当前趟剩余容量。如果在趟数相同的情况下选择剩余容量最大的状态那么对未来一定更有利——它给了后续人员更多“搭便车”的机会不会比剩余容量小的状态更差。这种“先比趟数再比last”的序关系是这道题DP能够正确收敛的关键。如果你想知道更严谨的证明可以这样想对于任意两个状态mask若dp1dp2则状态1一定不劣若dp1dp2且last1≤last2则状态1的“未来可行集合”包含状态2的“未来可行集合”因为载重余量更宽裕。所以这种偏序关系保证了最终全局最优解不会被剪掉。3. 位压缩与集合表示如何把一个“谁坐电梯”的问题塞进int里3.1 把人员集合编码成maskn最多20所以可以用一个int的二进制位来表示集合。第i位为1表示当前已经上了电梯0表示还没上。比如mask的二进制是10101在二进制下对应的人0、2、4从低位起已经在电梯里。这个思想叫“状态压缩”或者“bitmask DP”是处理小规模组合爆炸问题的基础武器。初始化的时候没人上电梯所以mask0dp[0]1last[0]0。注意这里dp初始化为1而不是0是因为即使一个人没上你也知道至少需要“准备一趟空电梯”。当然也可以初始化为0然后转移时强制新开一趟但两种写法等价的背后是你需要在代码里定义一个“空状态”的语义。我习惯的写法是dp[0] 1last[0] 0然后从mask0开始循环到mask(1n)-1。每一次都遍历未上电梯的人i看能转移到哪个新状态。新状态newmask mask | (1i)然后按照上面说的规则做更新。3.2 遍历子集和超集的两种思路一种做法是外层枚举当前mask内层枚举不在mask中的人。这种做法比较直观时间复杂度O(2^n * n)n20时大约是2000万次状态转移完全可接受。另一种做法是枚举“上一状态premask”通过添加一个人生成新状态。写起来差别不大。但我要提醒一点如果你想用记忆化搜索递归写DP要注意dfs的深度和子状态重复计算的问题。迭代式DP在这道题里代码更简洁推荐使用。下面直接给一份可运行的参考代码语言用C因为比赛环境里最通用#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, x; cin n x; vectorint w(n); for (int i 0; i n; i) cin w[i]; int total 1 n; vectorint dp(total, 1e9); vectorint last(total, 0); dp[0] 1; last[0] 0; for (int mask 0; mask total; mask) { if (dp[mask] 1e9) continue; for (int i 0; i n; i) { if (mask (1 i)) continue; // 已经上电梯 int newmask mask | (1 i); int newdp dp[mask]; int newlast last[mask] w[i]; if (newlast x) { newdp; newlast w[i]; } if (newdp dp[newmask]) { dp[newmask] newdp; last[newmask] newlast; } else if (newdp dp[newmask] newlast last[newmask]) { last[newmask] newlast; } } } cout dp[total - 1] \n; return 0; }这段代码的核心逻辑就藏在那两条if判断里。很多人会漏掉条件“newdp dp[newmask] newlast last[newmask]”这个分支结果答案偏大因为状态即使趟数没变剩余容量却被浪费了。4. 进阶优化去掉无效状态用滚动思路降低常数4.1 剪枝与状态压缩的边界上面代码的时间复杂度是O(2^n * n)n20时约为2000万次循环通常能在几十毫秒内跑完不需要额外优化。但如果你在别的OJ上遇到n22甚至更大就得考虑优化。一种常见的剪枝是提前终止。如果我们已经发现dp[total-1]被更新成某个值并且当前mask的dp值已经大于等于这个值那就不必再转移了。不过这属于常数级别的优化不能改变复杂度量级。另一种思路是在枚举未上电梯的人时只枚举“比当前mask中最低位更高位”的人。因为mask中已经包含的人不可能再上而未上的人之间无顺序差异所以重复枚举会浪费一定时间。但这个优化收益很有限不建议为了这点常数把代码写复杂。4.2 分成上下界的子集枚举法如果n超过22标准做法是把n个人平均分成两部分各自预处理“子集体重和不超过x”的最小趟数再合并两边的结果。这种“折半枚举合并”的思路可以处理n≤40的规模。对这道题来说n20完全够用但如果你准备基于这道题去学更进阶的“meet-in-the-middle”那不妨把上面的代码先吃透再去练折半枚举。4.3 位运算细节与性能小坑我在本地实测的时候发现一个问题如果直接在循环里用vector存取dp和last有些环境开了debug模式会跑得慢很多。比赛时尽量用std::array或C风格数组或者至少开O2优化。位运算时mask (1 i)的效率足够高但要注意1 i的类型是inti31时可能溢出本题n20无此问题但是代码习惯上建议写成1LL i或者(1u i)来避免隐患。此外vectorint dp(total, 1e9)一种常见的坑是如果初始化值设得太大累加last时可能超出int范围。本题体重上限通常是1e9以内last最大也是x不会爆int。但如果换题建议开long long。5. 常见问题与实战踩坑记录5.1 为什么样例过得了但交上去WA我最初写这道题时犯过一个特别经典的错误。我写状态转移时只用“dp值更小”作为唯一更新条件没有考虑“dp值相等但last更小”的情况。结果就是前几组样例全过但一到大数据就WA。后来我把else if (newdp dp[newmask] newlast last[newmask])这条分支补上问题立刻消失。这个错误非常值得拿出来说。因为很多DP题确实只需要一个数组就能搞但这道题的核心标志就是两个维度共同决定状态优劣漏掉任何一个最终都会被构造样例击穿。以后遇到“求最小趟数/最少组数”并且还附带“剩余容量”类约束的题都要警惕二维DP状态。5.2 初始化dp为0还是1的困惑看题解时有的代码初始化为0有的初始化为1很多新手就懵了。两种写法本质上都可以只要转移一致。关键是理解“空电梯”和“已有一趟”之间的语义。如果dp[0]0那么第一次塞人进去时因为last[0]0w[i]≤x一定成立所以走“不新增趟数”的分支但显然你不可能第一个人不占一趟。所以这种初始化下必须专门加判断当mask0时强制开一趟或者初始化改为dp[0]1。我建议直接用dp[0]1这样语义上最顺电梯一开始就是空的等第一波人。5.3 多个人体重相同会不会引起位运算重复计算体重相同的不同两个人仍然是两个不同的人状态压缩时他们对应的位不同所以不会出现重复。但有一种情况需要小心如果题目改成“人不可区分”那么状态压缩会浪费大量状态但本题人本身就是可区分的个体位运算完全没问题。5.4 输出格式答案是dp[total-1]还是dp[total-1]1这取决于初始化方式。用dp[0]1的方案最后输出dp[(1n)-1]就是正确答案。如果初始化成0且没有特殊处理就要在输出时加1或者在转移时统一加。我的建议是直接用dp[0]1省去输出时纠结。这里还有个容易忽略的细节如果n0即没有人坐电梯那答案应该是0。但本题n至少为1所以不处理也行。做题时还是习惯性考虑一下边界省得在极端输入下翻车。5.5 小样例手算验证法自己写完之后我建议你手动构造一组样例验证n4x10w[6,5,5,4]预期答案2趟。组合可以是64一趟55一趟。怎么确认你的DP输出对不对跑完代码再手推一遍看看。这类手推样例最大的价值不是验证代码“能跑”而是验证你对状态转移规则的理解。如果代码输出3那说明转移条件写错多半就是漏了last的更新。6. 从这道题延伸出去的DP思维模式6.1 什么时候该用状态压缩DP很多朋友学状态压缩DP时总觉得这玩意儿就是为了处理“n≤20的集合问题”而生的。这话没错但不够精确。更精准的判定标准是三件事同时成立数据范围小到2^n可接受通常n≤20~22问题是在一个集合上寻找最优划分/排列/子集组合子问题之间存在重叠且可以用位掩码唯一表示“已处理部分”。只要这三条同时满足就可以往状态压缩DP上想。比如旅行商问题、集合覆盖、任务调度的最小时间安排、甚至某些棋盘覆盖计数问题都可能用到类似思路。6.2 双数组DP状态的设计套路这道题里dp和last的关系可以抽象成一种更通用的模式主状态趟数 辅助状态剩余容量。很多问题表面上是单目标优化但解空间里隐藏着“同一主状态下谁更优”的比较。遇到这种问题时不要拘泥于单一数组可以先想清楚影响未来决策的因素有哪些给每个因素一个维度然后在更新时按优先级依次比较。举一个类似题将n个任务分配给k个工人每个任务有耗时求最小完工时间。这道题也可以用类似的双数组DP一维记录“已分配任务集合”另一个字段记录“当前最后一名工人的剩余可分配时间”。道理基本一致学会Elevator Rides之后这类题应该能举一反三。6.3 从DFS到递推的转化技巧状态压缩DP还有一种常见写法是DFS记忆化。对Elevator Rides来说DFS的好处是代码逻辑直观坏处是递归栈和常数。我建议你迭代版本和DFS版本都写一遍因为很多变种题用DFS更好想比如需要带路径回溯的题。DFS版的核心伪代码如下int solve(mask) { if (mask full) return 0; // 枚举所有未上电梯的人尝试加入当前趟或新开一趟 }但注意这种写法里趟数和last都要作为参数或数组缓存。你可以用一个pairint,int作为记忆化键值或者分成两个数组。迭代写久了之后你会发现DFS写法的状态更新更加直观排错更方便。6.4 状态压缩DP的典型复杂度估算实际做题时估算复杂度是基本功。n20时状态数是2^20≈1048576内层需要枚举n个人总操作约2000万次。C在1~2秒内能轻松跑完Python理论上也行但要注意常数优化比如把体重存在list里而不是字典。Python实现中循环1000万次以上就容易TLE建议用PyPy并尽量用位运算避免在循环里调用函数。日常比赛中如果碰到n22状态数变成400万操作约8800万次C勉强OKPython就要小心了。此时可以考虑折半枚举把复杂度降到O(2^(n/2) * something)或者用双向BFS。7. 我个人写这道题的一些体会与扩展建议说实话“Elevator Rides”这道题的难度在CSES里属于中等偏下但它的思想价值远高于题目本身的分数。它教会了我在状态压缩DP里非常重要的一个习惯永远问自己同一个dp值下还有没有其他状态信息需要维护。不能因为dp值相同就觉得“反正一样”。很多题目卡人的点恰恰是这种“看起来一样、实际不一样”的隐藏信息。如果你打算继续刷状态压缩DP的题我建议按照这个顺序来先做Elevator Rides彻底理解dplast这种双数组写法做Hamiltonian Flights同样是CSES题单里的TSP理解mask状态下“最后一个点”的信息怎么记录做Counting Tilings或者类似棋盘覆盖题理解轮廓线DP和逐格DP的差异做n40级别的“折半枚举”题学会把2^n缩减成2^(n/2)。按这个路径走下来状态压缩DP的核心打法就基本成型了。另外写这道题时我个人有个小习惯把所有中间状态打印出来观察。比如把mask循环到第几个查看dp[mask]和last[mask]的分布对着小数据手推一遍很容易定位到转移条件错误。调试状态压缩DP时打印状态图比打印最终答案有用得多。最后再分享一个小技巧如果在一场正式比赛里遇到这道换皮题比如改成“最少几辆车运走所有人”你不需要重新想算法只需要把“电梯载重上限”换成“车辆载重上限”体重数组换成包裹重量一套代码直接复用。能举一反三才是刷这道题最大的收获。