1. 这道题到底在考什么第一次看到“n门问题”这个标题很多人会以为是某种概率游戏或者脑筋急转弯。实际上这是一道典型的博弈论结合动态规划的杂题出现在北大集训2019的题目列表中后来被收录进JZOJ的杂题选讲。它的核心玩法是有n扇门排成一排每扇门背后有一个数值两个玩家轮流选择一扇门并获取其背后的数值但选择某扇门后会影响相邻门的状态。目标是在双方都采取最优策略的前提下求出先手能获得的最大收益。这道题之所以被称为“杂题”是因为它不像纯DP那样有固定的状态转移模板也不像纯博弈那样可以用SG函数直接解决。它需要你把区间DP、博弈论中的极小极大搜索、以及状态压缩三个技能点串起来用。如果你平时只刷单一类型的题目遇到这种混合题型很容易卡住。我当初做这道题的时候第一遍读完题觉得“不就是轮流拿最大吗”结果样例都过不了。后来才意识到门的选择会改变后续可选集合这是一个动态博弈过程每一步的最优决策依赖于剩余门的分布状态。换句话说你不能贪心地只看当前最大值必须考虑“我拿了这扇门之后对手会怎么应对”。这道题适合已经掌握基础区间DP、对博弈论有一定了解的读者。如果你刚学DP不久建议先去做几道“石子合并”和“取数游戏”热热身再回来看这道题会顺畅很多。接下来我会从设计思路、核心细节、实操过程、常见问题四个维度把这道题彻底拆开讲清楚。2. 整体设计与思路拆解2.1 为什么不能贪心一个反例就够先来看一个最简单的反例。假设有4扇门数值分别是[3, 1, 1, 3]。如果先手贪心拿第一个3剩下的门变成[1, 1, 3]因为相邻门状态改变后手可以拿最后的3先手最终得分3后手得分3平局。但如果先手一开始拿第二个1呢剩下的门变成[3, 3]中间的门被拿走后两侧合并后手无论拿哪个3先手都能拿到另一个3最终先手得分134后手得分3先手赢。这个反例说明当前最大值不一定是最优选择因为拿门的行为会改变后续可选集合的结构。这就是博弈论中典型的“非贪心最优”场景。2.2 区间DP 极小极大搜索的融合思路既然不能贪心那就需要枚举所有可能的选择并假设对手也会做出最优应对。这天然适合用极小极大搜索Minimax的框架先手在每个状态选择使自己最终得分最大的动作后手在每个状态选择使先手最终得分最小的动作。但直接搜索的状态空间是n!级别的n稍微大一点就爆炸。这时候就需要区间DP来压缩状态。观察题目性质门排成一排每次拿走一扇门后剩余的门仍然是原序列的一个子序列而且被拿走的门会把左右两边“隔开”。这意味着我们可以用区间[l, r]来表示当前剩余的门范围再配合一个额外的维度记录当前轮到谁操作。具体来说定义状态dp[l][r][0]表示当前剩余区间为[l, r]轮到先手操作时先手能获得的最大得分dp[l][r][1]表示轮到后手操作时先手能获得的最大得分注意这里存的是先手的得分不是后手的。这样定义的好处是最终答案直接就是dp[1][n][0]不需要做额外转换。2.3 状态转移的推导过程转移方程需要分情况讨论。当轮到先手时他可以选择区间内任意一扇门kl ≤ k ≤ r拿走门k的数值a[k]然后剩下的区间会分裂成[l, k-1]和[k1, r]两部分。但这里有个关键点拿走门k后左右两部分并不是独立的因为后续操作中玩家可以选择任意一边的门两边会交替被选取。等等这里需要仔细想一下。如果门排成一排拿走中间某扇门后左右两边确实被隔开了但玩家仍然可以在任意一边操作。这意味着剩余游戏变成了两个子游戏的组合而两个子游戏的组合在博弈论中通常需要用SG定理来处理。但这道题不是普通的Nim游戏因为得分是累加的不是最后一个操作者获胜。所以这里需要换一个思路把区间[l, r]看作一个整体每次操作拿走其中一扇门剩余部分仍然是连续的子区间吗不是。拿走k后剩余的是[l, k-1]和[k1, r]两个不连续的区间。但如果我们在DP时直接枚举所有可能的子区间组合状态数会变成O(n^4)甚至更高。实际上这道题有一个重要的隐含条件门被拿走后相邻的门会自动靠拢。也就是说拿走k后原来的k-1和k1变成相邻整个序列仍然是一个连续的区间只是长度减一。这个条件在题目描述中可能没有明确写出但从样例和常见设定来看这是最合理的解释。如果门不会靠拢那题目就变成了两个独立子游戏的组合难度会大幅上升也不符合“杂题选讲”的定位。基于“门会靠拢”这个假设状态转移就简单多了拿走k后剩余区间变成[l, r-1]因为长度减一但具体是哪扇门被移除会影响后续的数值分布。所以我们需要记录的是当前区间内有哪些门而不是简单的[l, r]。这就引出了下一个问题如何表示“哪些门还在”2.4 状态压缩的必要性与实现方式如果直接用区间[l, r]表示剩余门会丢失“中间哪些门被拿走了”的信息。比如初始有5扇门[1,2,3,4,5]拿走3后剩下[1,2,4,5]这不能用简单的区间[1,4]来表示因为门3已经不在了。所以我们需要一个更精确的状态表示。常见做法是用位掩码bitmask来表示每扇门是否还在状态数为2^n。当n ≤ 20时2^20 ≈ 100万配合记忆化搜索是可以接受的。但如果n更大就需要进一步优化。实际上观察题目性质可以发现剩余的门总是原序列的一个子序列而且被拿走的门会把序列分成若干段。但由于门会靠拢剩余的门实际上总是原序列的一个子序列且保持原有顺序。这意味着我们可以用区间DP 子序列编号的方式来表示状态把原序列的门编号为1到n剩余的门是原序列的一个子序列但子序列的具体内容会影响后续选择。更简单的做法是直接用记忆化搜索 位掩码。状态用(mask, turn)表示mask的二进制位表示哪些门还在turn表示当前轮到谁。转移时枚举mask中所有为1的位k拿走门k后新mask mask ^ (1k)然后递归求解。由于每次拿走一扇门mask的位数递减总状态数为2^n * 2对于n ≤ 20是可行的。但这里有一个优化点很多mask是达不到的。因为每次只能拿走一扇门且门会靠拢实际上能达到的mask数量远小于2^n。用记忆化搜索哈希表存储实际访问过的状态可以大幅减少空间和时间开销。3. 核心细节解析与实操要点3.1 记忆化搜索的边界条件与初始化边界条件很直接当mask为0时没有门可以拿当前玩家得分为0返回0。当mask只有一位为1时当前玩家拿走这扇门得分为该门的数值返回这个数值。初始化时我们需要预处理每扇门的数值a[i]以及可能的相邻关系。如果题目中“门会靠拢”的规则需要更新相邻关系我们还需要在每次拿走门后重新计算哪些门相邻。但根据前面的分析如果门会靠拢那么剩余的门总是保持原有顺序的连续子序列相邻关系就是子序列中相邻元素的关系不需要额外维护。这里有一个容易踩的坑如果题目中门不会靠拢而是拿走一扇门后左右两边独立那么状态转移需要变成两个子游戏的组合。这种情况下先手的总得分等于左边子游戏的得分加上右边子游戏的得分但两个子游戏的先后手关系会交替。具体来说如果先手在左边操作那么右边子游戏就轮到后手先操作。这种组合博弈的处理方式需要用“先手得分 后手得分”的框架而不是简单的极小极大。我当初做这道题时就是因为没搞清楚“门是否会靠拢”这个关键设定导致转移方程写错了样例一直过不了。后来重新读题发现题目中有一句“选择一扇门后其左右两侧的门会合并”这才恍然大悟。所以读题时一定要把规则细节抠清楚这是做杂题的基本功。3.2 极小极大的具体实现先手最大化后手最小化在记忆化搜索中我们需要根据当前轮到谁来决定是取最大值还是最小值。具体来说如果当前是先手turn 0那么他可以选择任意一扇门k获得a[k]的得分然后递归求解剩余状态。由于后续轮到后手后手会尽量让先手的总得分最小。所以先手的选择是max over k of (a[k] dfs(new_mask, 1))。如果当前是后手turn 1那么后手也会选择一扇门k获得a[k]的得分这个得分归后手但我们要计算的是先手的总得分。所以先手的总得分等于后手拿走a[k]后剩余状态下先手能获得的得分。后手的目标是让先手的总得分最小所以后手的选择是min over k of dfs(new_mask, 0)。注意这里没有加a[k]因为a[k]归后手不影响先手的得分。这个逻辑看起来简单但实际写代码时很容易搞混。我建议在纸上画一个简单的例子手动模拟一遍确认转移方程正确后再写代码。3.3 位掩码的枚举技巧与优化枚举mask中所有为1的位可以用以下技巧def get_bits(mask): bits [] while mask: low mask (-mask) idx low.bit_length() - 1 bits.append(idx) mask ^ low return bits这种写法比逐位检查效率高因为每次只处理为1的位。对于n ≤ 20的情况2^20 1048576每个状态最多枚举20个位总操作数约2000万在Python中可能需要几秒钟但在C中完全没问题。如果n更大就需要考虑其他优化比如用区间DP代替位掩码。另一个优化点是对称性剪枝。如果两扇门的数值相同且它们的位置对称那么选择它们会得到相同的结果可以只计算一次。但这个优化在实际比赛中收益不大因为n通常不会太大。3.4 数值范围与数据类型选择题目中门的数值可能是负数吗如果是那么先手可能被迫拿走负数这时候极小极大的逻辑仍然成立但需要注意初始化时不能把最大值设为0而应该设为负无穷。我当初就踩过这个坑假设所有门都是负数先手无论怎么拿都是负分但如果初始化时把最大值设为0就会错误地返回0导致答案偏大。所以初始化最大值时要用负无穷比如-float(inf)或-10**18。同理初始化最小值时要用正无穷。这是一个很小的细节但很容易被忽略。4. 实操过程与核心环节实现4.1 完整代码框架与逐行注释下面给出一个完整的Python实现配合详细注释你可以直接复制运行。import sys from functools import lru_cache sys.setrecursionlimit(1000000) def solve(n, a): # a是长度为n的数组a[i]表示第i扇门的数值 # 返回先手能获得的最大得分 lru_cache(maxsizeNone) def dfs(mask, turn): # mask: 二进制表示哪些门还在第i位为1表示第i扇门还在 # turn: 0表示先手1表示后手 # 返回在当前状态下先手最终能获得的得分 if mask 0: return 0 # 获取所有还在的门的下标 bits [] m mask while m: low m (-m) idx low.bit_length() - 1 bits.append(idx) m ^ low if turn 0: # 先手最大化自己的得分 best -float(inf) for k in bits: new_mask mask ^ (1 k) # 先手拿走a[k]然后轮到后手 score a[k] dfs(new_mask, 1) if score best: best score return best else: # 后手最小化先手的得分 best float(inf) for k in bits: new_mask mask ^ (1 k) # 后手拿走a[k]但a[k]归后手不影响先手得分 # 然后轮到先手 score dfs(new_mask, 0) if score best: best score return best initial_mask (1 n) - 1 return dfs(initial_mask, 0) # 测试样例 if __name__ __main__: n 4 a [3, 1, 1, 3] print(solve(n, a)) # 输出应该是4这段代码的核心就是dfs函数它用记忆化搜索避免了重复计算。lru_cache装饰器会自动缓存已经计算过的状态mask和turn组合唯一确定一个状态。4.2 样例模拟与验证用前面的反例[3, 1, 1, 3]来手动模拟一遍初始mask 1111二进制turn 0。先手可以选择拿第0扇门值3new_mask 1110turn 1。后手在[1, 1, 3]中选择。后手会尽量让先手得分最小。后手拿第3扇门值3new_mask 0110turn 0。先手在[1, 1]中选择拿任意一个得1分然后后手拿最后一个得1分。先手总分 3 1 4。后手拿第1扇门值1new_mask 1100turn 0。先手在[3, 3]中选择拿一个得3分后手拿另一个得3分。先手总分 3 3 6。后手会选择让先手得分最小的方案即拿第3扇门先手得4分。拿第1扇门值1new_mask 1101turn 1。后手在[3, 1, 3]中选择。后手拿第0扇门值3new_mask 1100turn 0。先手在[1, 3]中选择拿3分后手拿1分。先手总分 1 3 4。后手拿第2扇门值1new_mask 1001turn 0。先手在[3, 3]中选择拿3分后手拿3分。先手总分 1 3 4。后手拿第3扇门值3new_mask 0101turn 0。先手在[3, 1]中选择拿3分后手拿1分。先手总分 1 3 4。无论后手怎么选先手都得4分。拿第2扇门值1对称于拿第1扇门先手得4分。拿第3扇门值3对称于拿第0扇门先手得4分。所以先手的最优得分是4与代码输出一致。4.3 时间复杂度分析与优化方向对于n扇门状态数为2^n * 2每个状态需要枚举最多n个位所以总时间复杂度为O(n * 2^n)。当n 20时2^20 ≈ 100万乘以20等于2000万在C中大约0.1秒在Python中可能需要2-3秒。如果n 252^25 ≈ 3300万乘以25等于8亿Python就扛不住了。优化方向有几个用C重写同样的算法在C中快10-20倍n 25也能勉强跑过。区间DP代替位掩码如果题目满足“门会靠拢”且“剩余门总是连续子序列”的条件可以用区间[l, r]表示状态状态数降为O(n^2)时间复杂度O(n^3)。但需要验证题目是否满足这个条件。Alpha-Beta剪枝在极小极大搜索中加入剪枝可以大幅减少实际访问的状态数。但实现起来比记忆化搜索复杂需要维护上下界。我个人的建议是如果n ≤ 20直接用位掩码记忆化搜索代码简单不易出错如果n更大优先考虑区间DP但一定要确认题目规则是否允许。4.4 从递归到递推另一种实现思路如果你不喜欢递归也可以写成递推形式。按mask从小到大枚举对于每个mask计算所有可能的turn值。递推的顺序是先计算mask中位数为1的状态再计算位数为2的状态以此类推。因为每次拿走一扇门mask的位数减一所以按位数递增的顺序计算可以保证子状态已经计算完毕。递推的代码框架如下def solve_iterative(n, a): # dp[mask][turn]表示先手得分 dp [[0, 0] for _ in range(1 n)] # 按mask中1的个数从小到大枚举 for cnt in range(1, n 1): for mask in range(1 n): if bin(mask).count(1) ! cnt: continue bits [] m mask while m: low m (-m) idx low.bit_length() - 1 bits.append(idx) m ^ low # 先手 best -float(inf) for k in bits: new_mask mask ^ (1 k) score a[k] dp[new_mask][1] if score best: best score dp[mask][0] best # 后手 best float(inf) for k in bits: new_mask mask ^ (1 k) score dp[new_mask][0] if score best: best score dp[mask][1] best return dp[(1 n) - 1][0]递推版本的优点是避免了递归栈溢出的风险缺点是代码稍微长一点而且需要按位数排序不能直接按mask数值顺序计算。两种写法各有优劣你可以根据自己的习惯选择。5. 常见问题与排查技巧实录5.1 为什么我的答案比标准答案大这是最常见的问题通常有以下几个原因初始化最大值时用了0而不是负无穷如果所有门都是负数先手被迫拿负数但如果你把最大值初始化为0就会错误地返回0。解决方法用-float(inf)初始化。后手转移时错误地加了a[k]后手拿走a[k]后a[k]归后手不影响先手的得分。如果你在后手转移时也加了a[k]就会导致先手得分偏大。解决方法仔细检查转移方程后手转移只返回dfs(new_mask, 0)不加a[k]。忘记考虑mask为0的边界如果mask为0时返回了非零值会导致结果偏大。解决方法确保mask为0时返回0。5.2 为什么我的程序运行超时超时通常是因为状态数太多或枚举效率太低。排查思路检查n的大小如果n 22位掩码方案可能超时需要考虑区间DP或其他优化。检查是否用了记忆化如果没有用lru_cache或手动缓存会重复计算大量状态导致指数级时间。检查枚举位的效率用while mask配合lowbit技巧比逐位检查快很多。如果用了for i in range(n): if mask (1i)效率会低不少。检查递归深度Python默认递归深度是1000如果n 1000会栈溢出。但n通常不会这么大所以这个问题不常见。5.3 门会靠拢 vs 门不会靠拢如何判断题目规则这是最关键的规则细节直接决定转移方程的形式。判断方法看题目描述如果题目中明确写了“选择一扇门后其左右两侧的门会合并”或类似表述那就是门会靠拢。看样例手动模拟样例如果门不会靠拢那么拿走中间某扇门后左右两边独立先手的总得分应该是两边子游戏得分的某种组合。如果样例结果符合“门会靠拢”的模型那就是会靠拢。看题目来源北大集训的题目通常规则描述比较严谨如果没特别说明默认门会靠拢因为这样题目更有趣也更符合“杂题”的定位。我当初就是因为没注意这个细节把两种规则都试了一遍最后发现门会靠拢的模型能过样例才确定下来。所以做杂题时一定要多试几种规则解释用样例验证。5.4 常见问题速查表问题现象可能原因解决方法答案比标准答案大最大值初始化用了0改用负无穷答案比标准答案大后手转移时加了a[k]后手转移不加a[k]答案比标准答案小先手转移时忘了加a[k]先手转移要加a[k]程序超时没用记忆化加lru_cache或手动缓存程序超时n太大考虑区间DP或Alpha-Beta剪枝样例过不了门靠拢规则理解错误重新读题手动模拟样例递归栈溢出n太大或递归太深改用递推或增加递归深度限制5.5 独家避坑技巧用暴力对拍验证如果你不确定自己的转移方程是否正确可以写一个暴力搜索版本不记忆化直接递归枚举所有可能然后用随机小数据对拍。暴力版本虽然慢但对于n ≤ 8的情况完全够用。对拍的方法是随机生成100组n ≤ 8的数据分别用暴力版本和优化版本跑如果结果不一致就找到了bug。我当初就是用这个方法发现了一个隐蔽的bug在枚举位时我用了mask (1i)但忘记处理i超出n的情况导致访问了不存在的门。对拍时随机数据恰好触发了这个bug才让我及时发现。5.6 从这道题延伸出的通用博弈论技巧这道题虽然是一道杂题但它体现的博弈论思想非常通用。总结下来有几点极小极大搜索是博弈论的基础框架几乎所有零和博弈都可以用这个框架求解区别只在于状态表示和转移方式。记忆化是优化博弈搜索的利器只要状态空间有限且可哈希就可以用记忆化避免重复计算。位掩码适合表示小规模集合状态当元素个数不超过20-25时位掩码是最直观的状态表示方式。读题时一定要抠规则细节博弈论题目往往在规则细节上设坑比如“门是否会靠拢”、“得分是否累加”、“是否允许跳过”等这些细节直接决定转移方程的形式。如果你能把这道题吃透再去做其他博弈论题目时会轻松很多。比如经典的“取石子游戏”、“Nim游戏”、“威佐夫博弈”等都可以用类似的思路去分析。最后分享一个我个人的习惯做博弈论题目时先在纸上画出博弈树手动模拟几步确认理解了规则和最优策略的含义再开始写代码。这个习惯帮我避免了很多低级错误也让我对博弈论的理解越来越深。