前段时间在题库里刷到 P1196 这道题题面只有一句话一堆糖果摆在桌上两个玩家轮流从最左端或最右端取走一整堆谁拿到的糖果总数多谁赢。名字听着轻松真要写对可没那么简单。这篇解题报告就来完整复盘这道题它考的不是模拟而是区间 DP 加上两人零和博弈很多人第一眼会想到贪心但数据稍微刁钻一点贪心就会翻车。不管你是刚开始刷 DP 的初学者还是想在博弈类题目上积累套路的老手这篇文章应该都能给你点东西。这篇题解我尽量写得像一次完整的现场复盘从题目怎么读懂到贪心为什么错再到如何定义状态、推导转移、写出代码最后把我调试时踩过的坑和扩展思路也一并放上来。你不需要有很深的算法基础只要会基础的动态规划和一点点博弈直觉全程跟下来应该没有压力。1. 题目回顾与核心考点1.1 我读到的题面先把我刷到的题面整理一下方便后面展开分析。题目大概是这样描述的有 N 堆糖果排成一行第 i 堆里有 a[i] 颗糖果。两个人轮流行动每轮可以从当前序列的最左端或最右端取走一整堆糖果。两人都足够聪明目标是让自己最终拿到的糖果总数尽可能多。假设先手先行动问先手最终最多能拿到多少颗糖果。这个版本应该是比较常见的“取石子/取糖果”变种。原题可能会有多组数据或者数据范围不同但核心模型是一样的。我按最典型的约束来分析N 最大到 1000 左右a[i] 可能达到 10^5所以所有糖果加起来可能超过 2^31代码里必须用 long long 存总和和 DP 值这个细节后面还会再提。1.2 一眼看上去像什么题这里值得多说一句。P1196 这个名字容易让人以为是一道很水的模拟题实际情况恰恰相反。两个玩家轮流从两端取这个操作模式太有迷惑性了——大多数人的第一反应是“每次取两端较大的那堆不就行了”。这种思路对应的是贪心在某些数据下确实能拿高分但题目里有一句很关键的话“两人都足够聪明”。这四个字意味着双方都在做最优决策你取走一堆之后剩下的局面轮到对手做最优选择你的收益会被对手的决策直接影响。这就不是简单的“每次取最大”能解决的问题了而是典型的零和博弈动态规划问题。我个人的习惯是看到“轮流取”“两端取”“都足够聪明”这几个关键词马上在脑子里标记出三个候选算法方向贪心、区间 DP、博弈论比如 SG 函数。然后通过手推小数据排除不可能的方案。下面这一节我会用一组真正让贪心崩盘的数据来做排除这个过程比直接给出结论更有价值。2. 从反例说起贪心为什么错2.1 一个让贪心崩盘的数据为了验证贪心到底行不行我构造了一组数据当时手推完差点把笔扔掉糖果序列2, 8, 3, 4, 5, 1如果按“每次取两端较大的一堆”来玩过程是这样的先手看到最左是 2最右是 1于是取走 2。后手看到最左是 8最右是 1于是取走 8。先手看到最左是 3最右是 1于是取走 1。后手看到最左是 3最右是 5于是取走 5。先手看到最左是 3最右是 4于是取走 4。后手取走最后的 3。最终先手拿到 2147后手拿到 85316。先手输得相当惨。但如果你用最优策略去算先手第一手应该取最右边的 1最终先手可以拿到 13后手只能拿到 10。同样是这组数据贪心只能拿 7最优解能拿 13差距非常大。这组数据直接否掉了贪心方案。我当时的第一反应是“这组数据是不是太刻意了”但后来仔细想了想它其实精准地抓住了贪心的命门贪心只看当前两端的大小完全忽略了两端背后的结构。2.2 为什么“眼前的最大”不可靠这组数据里最关键的错位在于先手第一步面临的是“取左端 2”还是“取右端 1”的选择。单看两端2 显然比 1 大贪心自然选 2。可是取走 2 之后左边第二大堆 8 就暴露出来了后手下一手直接拿走 8。这个 8 就像是藏在 2 背后的一颗雷谁先碰 2谁就是把 8 送给对手。反过来如果先手第一步取右端的 1虽然这一步少拿了一颗糖但是右边的 5 被保留下来后手如果贸然取 2就会把 8 暴露给先手如果后手取 5右边的结构又没有崩坏。整个局面的主动权反而被先手掌握住了。这就是零和博弈和普通贪心最大的区别在贪心里你只需要保证自己这一步最好在博弈里你还要考虑“我做了这个选择之后对手会怎么反击”。一个好的决策不是让自己眼前收益最大而是让对手后续能占的便宜最小。想明白这一点整个题目的方向就清晰了——它是一道博弈视角下的区间 DP。3. 区间 DP 模型定义状态写出转移3.1 状态定义谁在哪个区间做决策既然游戏过程是不断从序列两端取走元素那么任意时刻剩下的糖果一定还是连续的一段区间。这个性质非常重要它决定了这个问题可以用区间 DP 来刻画。假设当前剩下的区间是 [i, j]轮到某一位玩家行动这位玩家面临的局面用 dp[i][j] 来表示。我采用的定义是dp[i][j] 表示“在当前区间 [i, j] 上进行最优博弈时当前行动者最终能获得的最大糖果总数”。注意“当前行动者”这个说法它不代表先手或者后手而是代表“轮到我行动的那个人”。游戏是交替进行的所以我只需要关心“当前这个人”不需要区分姓名。有了这个状态边界情况也很好写当 i 等于 j 时区间里只剩一堆糖果当前行动者直接取走所以 dp[i][i] a[i]。3.2 转移方程把自己代入“下一回合的对手”当前玩家在区间 [i, j] 上只有两个选择取左端 i或者取右端 j。如果取左端 i那么当前玩家先拿到 a[i]剩下的区间变成 [i1, j]轮到对手行动。对手在这个剩余区间里同样会采取最优策略也就是说对手能拿到 dp[i1][j] 颗糖果。剩余区间总共有多少颗糖果呢可以用前缀和快速算出来sum(i1, j) 总糖果数 sum(i, j) - a[i]。对手拿完之后剩余的所有糖果都是当前玩家的所以当前玩家从这条路能获得的总数就是a[i] (sum(i, j) - a[i] - dp[i1][j]) sum(i, j) - dp[i1][j]这里有一个非常关键的理解点当前玩家取走 a[i] 后接下来的游戏就变成了对手在 [i1, j] 上“作为当前行动者”去做最优决策。对手拿得越多当前玩家拿得就越少所以要用剩余区间的总糖果数减去对手的最优收益剩下的才是当前玩家最终能拿到的数量。同理如果取右端 j那么当前玩家能拿到的总数是 sum(i, j) - dp[i][j-1]。当前玩家会在这两个选择里挑收益更大的那个所以转移方程是dp[i][j] max(sum(i, j) - dp[i1][j], sum(i, j) - dp[i][j-1])注意到方程两边都含 sum(i, j)所以这个式子可以进一步写成dp[i][j] sum(i, j) - min(dp[i1][j], dp[i][j-1])这个等价写法非常耐人寻味当前玩家在两端之间做选择本质上是让对手在“去掉左端后的区间”和“去掉右端后的区间”这两个局面里拿到更少的那一个。这个视角可以帮你快速理解为什么博弈类区间 DP 的核心是“替对手考虑”。3.3 前缀和优化一次预处理搞定区间和转移方程里反复用到 sum(i, j)如果每次都用循环累加复杂度会多一个 N总复杂度变成 O(N^3)在 N1000 时大约 10^9 次运算基本跑不动。所以需要前缀和数组做预处理。前缀和的定义很常规pre[i] 表示前 i 堆糖果的总数也就是 pre[i] pre[i-1] a[i]。初始化时 pre[0] 0。那么区间 [i, j] 的糖果总数就是 pre[j] - pre[i-1]。这个预处理是一次 O(N) 的循环之后任意区间的和都能在 O(1) 时间内拿到。整个 DP 的时间复杂度就变成了 O(N^2)N1000 时只有约 10^6 次状态计算属于非常轻松的量级。3.4 两种等价写法总数版与净差版上面的 dp[i][j] 表示的是“当前玩家在该区间能拿到的糖果总数”。还有一种非常流行的写法定义 f[i][j] 为“当前玩家最终糖果数减去对手最终糖果数的差值”。转移方程是这样的f[i][j] max(a[i] - f[i1][j], a[j] - f[i][j-1])这个方程的思路是当前玩家取走 a[i] 后对手在 [i1, j] 区间里会追求让自己和当前玩家的差值最大化但注意此时当前玩家和对手的角色互换了所以对手追求的“最大差值”就是 f[i1][j]。站在当前玩家的角度自己的最终总收益减去对手的总收益就等于 a[i] 减去对手在下一阶段建立起来的差值。两个方向取较大者即可。这个净差版的最终答案怎么算设整段糖果的总和为 total先手和后手的总数分别是 X 和 Y。那么有 X Y total且 X - Y f[1][N]。解这个二元一次方程组得到X (total f[1][N]) / 2如果题目只要求输出先手最多拿多少用总数版 dp[1][N] 直接就是答案不用再除以二代码更直观。净差版的好处是状态值可能更小而且转移方程形式上更像“吃糖果游戏”这类博弈题的模板。两种写法我都实测过时间上没有本质区别选一种自己觉得顺手的就好。4. 代码实现与复杂度分析4.1 记忆化搜索思路直观适合快速验证如果你平时写 DP 习惯了先写暴力再优化这道题用记忆化搜索来做会非常舒服。C 代码长这样#include bits/stdc.h using namespace std; const int MAXN 1005; long long a[MAXN], pre[MAXN]; long long dp[MAXN][MAXN]; bool vis[MAXN][MAXN]; long long solve(int i, int j) { if (i j) return a[i]; if (vis[i][j]) return dp[i][j]; vis[i][j] true; long long sum pre[j] - pre[i - 1]; dp[i][j] max(sum - solve(i 1, j), sum - solve(i, j - 1)); return dp[i][j]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; for (int i 1; i n; i) { cin a[i]; pre[i] pre[i - 1] a[i]; } cout solve(1, n) endl; return 0; }记忆化搜索有个天然优势边界条件和递归顺序不用手动考虑只要保证递归函数里访问的子区间长度一定比当前区间短就不会出现重复计算或者访问未定义状态的问题。它还有一点很实用你可以在 solve 函数里加一句输出观察每个区间是怎么被递归访问的对调试和理解状态依赖关系都有帮助。4.2 递推实现按区间长度从小到大枚举竞赛里更推荐用递推写法因为省去了递归栈的开销虽然本题 N 不大递归也不会爆栈但递推代码的循环逻辑更容易对比复杂度。核心代码#include bits/stdc.h using namespace std; const int MAXN 1005; long long a[MAXN], pre[MAXN]; long long dp[MAXN][MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; for (int i 1; i n; i) { cin a[i]; pre[i] pre[i - 1] a[i]; } for (int len 1; len n; len) { for (int i 1; i len - 1 n; i) { int j i len - 1; if (len 1) { dp[i][j] a[i]; continue; } long long sum pre[j] - pre[i - 1]; dp[i][j] max(sum - dp[i 1][j], sum - dp[i][j - 1]); } } cout dp[1][n] endl; return 0; }外层循环必须先枚举区间长度 len内层再枚举左端点 i。为什么不能先枚举 i 再枚举 j因为 dp[i][j] 依赖的是 dp[i1][j] 和 dp[i][j-1]这两个状态的区间长度都比当前状态小 1。如果外层先枚举左端点那么当你计算 dp[i][j] 时dp[i][j-1] 可能已经算好了但 dp[i1][j] 不一定算好了因为它的左端点更大在当前 i 的循环里还没轮到。而按区间长度从小到大枚举所有长度更小的区间都已经算完依赖就不会出问题。这个顺序问题在一些写法里会导致答案完全不对调试成本很高后面我会再把它列为典型坑点。4.3 时空复杂度与实测数据状态数量是 N(N1)/2每个状态的转移是 O(1)所以时间复杂度是 O(N^2)。空间上需要 dp 二维数组也是 O(N^2)N1000 时大约 10^6 个 long long占 8MB 左右完全够用。如果 N 到 5000空间就会到 200MB这时可能需要考虑滚动数组优化这个我放在后面的扩展部分讲。我自己在 N1000、a[i] 随机取 1 到 1e5 的数据下跑递推版本总耗时在 10ms 以内。如果题目给了多组数据记得每次清空 dp 和 pre或者把 dp 数组直接初始化为 0 再重新覆盖否则会出很隐蔽的错。5. 现场调试我踩过的坑5.1 边界条件len1 和访问 n1边界条件是这类题翻车率最高的地方。len1 时区间只有一个元素dp[i][i] a[i]这个在前面已经说过。但在递推实现的循环里如果你把 len1 和 len1 的情况混在一起写很容易在 len1 时访问 dp[i1][j] 或 dp[i][j-1]而这两个状态对应的区间是不合法的。我建议在循环里显式判断 len1 单独处理代码虽然多两行但逻辑清晰很多。另外要注意数组下标越界。当 i1 时前面前缀和使用 pre[i-1] 就是 pre[0]所以 pre 数组大小至少开 n1。dp 数组我习惯多开几格比如 MAXN 定成 1005而实际 N 最大 1000这样即使某些循环不小心越界访问了 dp[i1] 里 i1 等于 n1 的位置也只是读到初始化值不会直接 RE。这个习惯在比赛里能救命。5.2 循环顺序为什么外层必须是 len这算是我踩过最深的坑之一。一开始我是这样写的for (int i 1; i n; i) { for (int j i; j n; j) { // 直接算 dp[i][j] } }这种写法在计算 dp[i][j] 时dp[i][j-1] 已经算过但 dp[i1][j] 还没算过因为外层是左端点从小到大当算到 dp[i][j] 时dp[i1][j] 要到下一轮 i1 才会被计算。于是很多状态会被跳过或读到 0结果完全不对。我的排查方式是在递推循环里加了临时输出把 (i, j) 和两个子状态 (i1, j)、(i, j-1) 的值都打出来对比手算的小数据立刻就能发现 dp[i1][j] 还是 0。后来改成外层枚举区间长度 len一切就正常了。这个经验我一直记着区间 DP 题外层循环几乎永远是区间长度。5.3 开 long long累加和可能超出 int题面说每堆糖果 a[i] 可能到 10^5N 到 1000那么总和最大到 10^8int 其实也装得下。但如果 N 到 10^5 或者 a[i] 更大总糖果数很容易达到 10^10 级别所以从写代码的第一步我就用 long long 存 a、pre 和 dp。别小看这个选择一旦后期数据变大排查溢出问题会非常痛苦。另一个容易被忽略的点是如果你用净差版 f[i][j]虽然 f 的值可能不大但最后算答案时 (total f) / 2 里的 total 也是 long long中间不要强转成 int。5.4 肉眼验数小样例怎么手推每次写完一个 DP我都会先手推一个 n3 和 n4 的小样例在草稿纸上把 dp 表格完整填一遍再和程序输出对比。这个小习惯看起来笨实际排查效率很高。比如序列 1, 100, 2肉眼就能看出先手取 2 后手取 100 先手取 1先手 3后手 100。但真正的最优是先手取 1后手取 2先手取 100先手 101后手 2。程序如果输出 3说明 DP 写错了如果输出 101至少在这一组上是正确的。手推 DP 表格的具体方法是先用 len1 填对角线然后 len2 填相邻的两个元素再逐步扩大区间长度。这个过程和递推代码的循环顺序完全一致你手推一遍等于把代码执行了一遍很多逻辑错误会在纸上自己暴露出来。6. 延伸思考吃糖果还能怎么考6.1 从线性变成环形把一排糖果首尾相接变成一个环是这类题最常见的变体。环形区间 DP 的标准套路是把原数组复制一份接到自己后面长度变成 2N然后在所有长度为 N 的区间里取最优答案。具体到这里就是遍历所有起点 s计算区间 [s, sN-1] 的 dp 值取最大值。这个技巧以后遇到“环形取石子”“环形合并果子”都能复用建议自己动手写一遍加深印象。6.2 限制每次取一堆之外的变体有些变体会在两端之外加上限制条件比如每次只能取不超过 k 堆、或者取走一堆后相邻的某些位置会被标记不可选。这些变体的状态往往需要扩维比如在 dp 数组上多加一维表示当前可选的堆数上限。核心思想不变当前玩家要保证自己选择后对手在剩余局面的收益尽量小。遇到这种题先画状态转移图找清楚子状态是什么再动手写代码。6.3 这类题的识别公式我把这类题的识别方法总结成一个“公式”两端取元素 两人轮流 都足够聪明大概率就是博弈型区间 DP。如果序列还可能被切成多段分别处理那就要考虑搜索或者状态压缩。反过来说如果题目只是单人在一个序列上取最大值没有对手博弈那可能就是普通的区间 DP 或者线性 DP状态定义和转移会简单不少。做题时先做类型识别比拿到题就硬套模板要重要得多。写了这么多最后分享一个我自己的小习惯遇到博弈型区间 DP我写完代码后不会直接交而是先跑一遍 n2 和 n3 的极端数据比如 [1, 100]、[1, 100, 1]确认边界和胜负关系都符合直觉再跑随机大样例。这套流程看着简单帮我挡住过很多次因为粗心导致的 RE 和 WA。希望这篇 P1196 的解题报告能帮你在下次遇到“两端取糖果”这类题时少走一点弯路。