今天是信奥打卡第 2685 天，随手点开题库先碰到的就是这道 P2998 [USACO10NOV] Candy S。题目名字带着糖，不少同学第一反应是“这不就是模拟发糖吗”，等真正开始写代码才发现，贪心推不动、搜索会超时，最后老老实实回到状态设计上。Candy S 的价值正在这里：它用一道银牌题的包装，把线性动态规划、状态压缩、边界处理这几个基本功全串在一起，适合刚学完基础 DP 想往竞赛难度过渡的人，也适合刷题打卡到中段需要总结套路的人。

这类题在 USACO 早期套题里非常典型。你不需要高级数据结构，甚至不需要多少 STL 花活，一支 vector、一个循环、几个 long long 变量就够了。可正因为代码短，考察点全部压在思路是否清晰上。接下来我会从拿到题目开始的思维过程讲起，把我踩过的坑、走过的弯路一起写出来，争取让你看完这篇就能照着推导同类问题。

1. 拿到题先别急着写：Candy S这题的考点拆解

1.1 题目到底在让你算什么

这题的题意在洛谷上有好几个翻译版本，我按自己刷到这个题时最接近 USACO 原题的一版来记。有一排糖果盒，编号 1 到 N，第 i 个盒子里放着 val[i] 颗糖。现在要从这一排盒子里选一些拿走，但是有一个硬性规定：相邻两个盒子不能同时拿。问最多能拿多少颗糖。

第一次读题，很多人会把这个“相邻不能同取”理解成“每隔一个格子取一个”。比如贪心地先对糖果数排序，或者直接隔一个取一个。可问题在于，糖果数量并不一定按位置单调排列，隔一个取不一定是最优的。你在 i 位置做出了“不拿”的决策，并不代表 i+1 就一定要拿，它也可以继续不拿。真正的决策点是“当前位置拿还是不拿”，而一旦决定拿，就压缩了下一个位置的决策空间。

这个模型看起来特别像“发糖模拟”，但本质上是典型的互补约束选择问题。决策只影响相邻位置，这类结构是动态规划最容易处理的形态之一。很多人卡在这一题，不是因为不会写代码，而是因为一开始把它当成纯模拟题，没有意识到自己面对的是一个带约束的最优化问题。

1.2 为什么贪心和暴力都容易翻车

先看贪心。很多人第一版会写成：把 val 复制一份按降序排，从头到尾能拿就拿。这个思路在一半的随机数据上看起来都对，但只要出现一堆特别大的数聚集在相邻位置，贪心就会先拿走其中最大的那个，然后导致旁边同样很大的数全部不能拿，总收益反而偏低。拿一个具体小例子来说，盒子序列是 5, 4, 5，如果贪心先取中间的 4，两边都废了，最后只能得 4；但要是不取中间，取两边的 5 和 5，总和是 10。这一组数据就能把贪心打回原形。

再看暴力。如果枚举所有拿取方案，每个盒子有拿和不拿两种状态，整体时间复杂度是 O(2^N)。银牌题不会给你太小的 N，一旦 N 到一万，这种指数级搜索连第一个测试点都过不去。中间可能碰到的剪枝技巧可以延长一点寿命，但无法解决本质问题。

那么动态规划为什么能用在这儿？因为它把“从 1 到 i 的最优解”作为子问题，而且 i 位置拿不拿只影响 i+1 位置的可用性，不会影响更远的位置。这种局部影响、整体最优的结构，正是 DP 的用武之地。你不需要知道前 i 个盒子具体怎么拿的，你只需要知道它们能带来的最大收益是多少，这就是 DP 状态设计的核心思想：丢掉过程细节，只保留与未来决策相关的信息。

1.3 三种模型的横向对比

这个表格不是让你记住结论，而是帮你建立“拿到一个优化问题先判断决策影响范围”的习惯。决策只影响固定近邻时，优先想到线性 DP；决策影响范围不断扩散时，才需要考虑区间 DP 或状态压缩。Candy S 的“相邻互斥”就是最简单的局部影响，所以线性 DP 是首选。我在带新人时经常说一句话：看到“相邻”“不能同时”“最大权值”这几个关键词凑在一起，第一反应就应该是 DP，而不是别的。

2. 核心推导：状态定义、转移方程与空间压缩

2.1 状态定义从哪里来

定义 dp[i] 表示从第 1 个盒子考虑到第 i 个盒子时，能拿到的最大糖果总数。这里不附加任何关于第 i 个盒子是否被拿的额外条件，也不区分“最后一个拿的是哪个位置”，只记录范围内的最优值。这样定义有一个明显好处：无论第 i 个盒子怎么决策，最终答案都能由 dp[i] 代表。

接下来拆分第 i 个盒子的决策：

• 不拿第 i 个盒子。那么第 i-1 个盒子本来就可以随便处理，问题直接变成了 dp[i-1]。
• 拿第 i 个盒子。那么第 i-1 个盒子一定不能拿，能用的最优基础是 dp[i-2]，再堆上 val[i]。

于是得到转移方程：dp[i] = max(dp[i-1], dp[i-2] + val[i])。这个方程总共三行，却是整道题的核心。初次接触的人容易把 dp[i-1] 误写成 dp[i-1] + val[i]，少考虑了“拿了第 i 个就必须放弃第 i-1 个”的约束，得到的结果会变成可以同时拿相邻两个盒子，与题意完全相反。

边界条件也要小心。当 i = 1 时，dp[1] = max(0, val[1])。加一个 0 是因为糖果数量可能有负值吗？在绝大多数类似题目中不会出现负糖果数，但如果你把这个问题扩展到带权值的情况，出现负数时“一个都不拿”也是合法决策，所以初始化为 0 是更稳妥的写法。当 i = 2 时，dp[2] = max(dp[1], val[2])，但如果你直接用转移方程代入 dp[i-2]，会发现 dp[0] 这一项需要人为定义成 0，不然数组访问就越界了。

2.2 从第一版递推到滚动数组

第一版可以老老实实开一个长度为 N 的 long long 数组：

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<long long> val(n); for (int i = 0; i < n; ++i) cin >> val[i]; if (n == 0) { cout << 0 << '\n'; return 0; } if (n == 1) { cout << max(0LL, val[0]) << '\n'; return 0; } vector<long long> dp(n); dp[0] = max(0LL, val[0]); dp[1] = max(dp[0], val[1]); for (int i = 2; i < n; ++i) { dp[i] = max(dp[i - 1], dp[i - 2] + val[i]); } cout << dp[n - 1] << '\n'; return 0; }

这份代码在数据范围不大时完全够用。但我习惯刷题时顺手优化空间，因为竞赛里的 N 很可能到 10^5 甚至 10^6，虽然开一个 vector 也就是 8 兆字节，不会有事，但养成长度意识没有坏处。你仔细观察转移方程，dp[i] 只依赖 dp[i-1] 和 dp[i-2]，再往前的结果已经永远不会再参与计算。这意味着整个数组都可以扔掉，只留两个变量。

滚动后的递推写法如下：

long long pre = 0; // 相当于 dp[i-2] long long cur = 0; // 相当于 dp[i-1] for (int i = 0; i < n; ++i) { long long take = pre + val[i]; long long skip = cur; long long nxt = max(skip, take); pre = cur; cur = nxt; } cout << cur << '\n';

这个写法把 dp[i-1] 和 dp[i-2] 从数组里挪到了普通变量中。很多第一次接触滚动数组的人会在最后的变量更新上栽跟头。你要注意的是，nxt 计算完之后，原来的 cur 会变成下一轮的 pre，原来的 pre 则被彻底丢弃。如果顺序写成 pre = cur; cur = nxt 没有问题；但如果你先写 cur = nxt; 再写 pre = cur，那么两行代码实际上把同一个值赋给了 pre 和 cur，下一轮递推结果全错。这个错误非常隐蔽，因为编译不会报错，小数据也可能碰巧正确，只有特定数据点才会让你发现结果不对。

2.3 环形题变体：把首尾也变成邻居

有的题会在 Candy S 基础上多加一句：第 1 个盒子和第 N 个盒子也算相邻。此时原来的线性模型失效，因为你处理完最后一个位置时，会发现第一个位置是否被拿的信息还悬在那里，不在当前状态里。要处理环形约束，常见套路是拆成两类情况：

• 第 1 个盒子一定不拿，然后对第 2 到第 N 个盒子做普通线性 DP。
• 第 1 个盒子一定拿，这时第 2 个和第 N 个盒子都不能拿，所以相当于对第 3 到第 N-1 个盒子做普通线性 DP，最后补上 val[1]。

两条路线分别跑一遍，取较大值就行。这样就把环形问题拆成了两个线性问题。如果考试时遇到没有环形约束的版本，你不需要管这一段，但掌握了它，以后面对“首尾相接”的同类题就不会慌。我在实际刷题中发现，很多看起来是“新题”的题目，本质上就是在 Candy S 这种模型上加了环形、分组或者序列长度的限制而已。

3. 完整 C++ 实现：从能过样例到稳稳 AC

3.1 读入与输出要注意的细节

题目输入格式常规来说先给一个 N，第二行给 N 个糖果数。很多人在刷题打卡时喜欢用 cin，这在 N 不大的题目里没问题，但为了形成统一习惯，我只要做题都先写上 ios::sync_with_stdio(false) 和 cin.tie(nullptr)。两行代码可以让 cin 在大部分情况下不再拖后腿。你要是看到别人代码里写 scanf/printf，也别觉得高深，只是不同的风格选择。C++ 里用 cin 配 long long 足够。

存储糖果数时直接用 vector ，千万别贪方便写 int。糖果数量本身看着不大，但动态规划在递推过程中要把很多位置的糖果累加在一起，一旦 N 到十万，总量就可能超过 int 上限。因为一个 int 溢出造成的 WA，我至少遇到过三次，每次都是查了半天才发现类型问题。你现在养成这个习惯，以后遇到更大数据范围的题目才会少走弯路。

3.2 线性版本的完整可运行代码

下面是这份题最常用的一版实现：

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; if (!(cin >> n)) return 0; vector<long long> val(n); for (int i = 0; i < n; ++i) cin >> val[i]; if (n == 1) { cout << max(0LL, val[0]) << '\n'; return 0; } long long pre = 0; // dp[i-2] long long cur = max(0LL, val[0]); // dp[i-1] for (int i = 1; i < n; ++i) { long long newCur = max(cur, pre + val[i]); pre = cur; cur = newCur; } cout << cur << '\n'; return 0; }

这份代码里，我把 pre 初始化为 0，cur 初始化为第一个盒子能带来的最优值。为什么要初始成 max(0LL, val[0]) 而不是直接 val[0]？因为我默认“可以不拿任何盒子”，尤其当 val[0] 是负数或题目允许空选择时，0 才是合理下界。如果确认数据全部非负，直接写 val[0] 也可以，但多写一个 max 能让代码更健壮。

循环从 i = 1 开始，拿 val[1] 与 cur 比较时，pre 正好是 dp[-1] 的位置，初始化为 0，语义上就是“只考虑前 0 个盒子时的收益是 0”。理解这个等价关系以后，你再看滚动数组就不会觉得它只是在炫技了。它的本质是把状态数组压缩成两个历史值，而这两个历史值的语义和完整数组完全一致。

3.3 如果需要处理环形版本

假设题目变成“首尾相邻”，我习惯封装一个函数 solve(l, r, val)，返回只考虑 [l, r] 区间的最大收益。然后用两种情况取最大值：

long long solve(const vector<long long>& val, int l, int r) { if (l > r) return 0; long long pre = 0; long long cur = max(0LL, val[l]); for (int i = l + 1; i <= r; ++i) { long long nxt = max(cur, pre + val[i]); pre = cur; cur = nxt; } return cur; } int main() { // 读入 val[0..n-1] // 情况一：不拿 val[0]，区间是 [1, n-1] long long ans1 = solve(val, 1, n - 1); // 情况二：拿 val[0]，则 val[1] 和 val[n-1] 都不能拿，区间是 [2, n-2] long long ans2 = (n >= 2 ? val[0] + solve(val, 2, n - 2) : val[0]); cout << max(ans1, ans2) << '\n'; }

这个封装的思路比在 for 循环里狂写特判要清晰。解题时最忌讳的就是在循环里到处修修补补，因为你补的每个条件都可能在另一个边界上漏 case。拆成子区间以后，每个子问题都是标准线性 DP，调试成本低很多。尤其是考试时间紧张的时候，清晰的子问题结构往往比“省一个函数调用”更重要。

3.4 复杂度与过题预期

整个算法的时间复杂度是 O(N)，空间复杂度是 O(1)（滚动变量版本）。即使 N 是 10^6，这个程序跑完也就是几十毫秒的事。USACO 银牌题的数据范围通常不会把这套方案的极限逼出来，所以你真正要担心的不是性能，而是思路和边界。换句话说，如果你 TLE，多半不是常数不够小，而是你用了不合适的算法；如果你 WA，多半不是代码写错，而是状态定义或转移方程在某一个边界上出了偏差。把注意力放在“状态定义对不对”上，永远比放在“要不要加优化指令”上更值得。

4. 调试与常见错误速查

4.1 数组越界和 n 的边界

最容易爆的第一处是 n = 1。很多模板代码默认 n >= 2，于是 dp[1] 这一行直接把数组越界读出去了。在 OJ 上，越界不一定会 RE，更可能把某个随机内存当成数值读进来，导致答案变成一个根本不存在的巨大数字。我处理所有 DP 题都会在开写之前先确认最小数据规模，尤其是 n = 0、n = 1、n = 2 这三个值，一定要单独跑一遍手算样例。

另外一个容易被忽略的问题是输入里可能多出空格或换行，尤其是从文件复制样例时。cin 会自动跳过空白，所以这个风险不大，但如果你用 scanf 读，就要小心格式串。大部分人不会在这一步出错，可一旦出错，现象会非常诡异，有时明明读到了 n，后面 val 数组却缺项。这种问题和你的算法没关系，纯粹是输入解析问题，排查时要先确认数据真的读进来了。

4.2 滚动变量的更新顺序

我已经在 2.2 那里提醒过一次，这里还要再说一次，因为这个错误太隐蔽了。滚动更新的正确顺序是：先算 nxt，再用 pre 覆盖旧 pre，最后 cur 接收 nxt。如果代码变成：

pre = cur; cur = max(cur, pre + val[i]);

你会发现等号右边的 pre 已经不是上一轮的 dp[i-2] 了，它已经被 cur 覆盖。这个 bug 几乎不报错，只在部分数据点输出错误答案，排查时特别费劲。我的习惯是给变量名起得足够长，oldPre、oldCur、newCur，宁可多敲几个字母，也不要让语义混淆。如果在赛场上实在不放心，先开数组写出正确版本，再在本地改成滚动版本，对照随机数据验证。这样能保证你优化完代码之后，逻辑没有发生任何变化。

4.3 负数糖果与答案下限

原题大概不会出现负糖果，但很多 OJ 的加强数据会把权值改成任意整数。一旦出现负数，“至少拿 0 个”和“必须拿满”就产生了区别。dp[0] 初始化成 0，表示空操作；如果初始化成 val[0]，万一 val[0] 是负数，你相当于被迫选了一个负收益盒子，答案会比真实最优值小。这个问题在力扣等平台上很常见，USACO 原题通常友好一些，但把你的代码写成能处理负值会更有通用性。

为了查错方便，我常会用下面这种临时输出：

cout << "i=" << i << " pre=" << pre << " cur=" << cur << '\n';

小数据下观察每一项的递推值与手算结果是否一致，一旦发现某一步开始出现异常，就顺着那一层往前找，基本都能定位。竞速刷题时可以不开调试输出，但阶段性打卡时慢一点反而是可取的。毕竟你写一篇解题笔记的目标是把这道题吃透，而不是只为了那一次 accept 的绿色提示。

4.4 常见错误速查表

这张表当然不能覆盖所有问题，但它是我复盘这道题时真实遇到过的五个类型。你可以把它当作自检清单，在提交之前逐条过一眼，很多隐藏问题会提前暴露。尤其是前三条，几乎是所有 DP 新手都会踩的组合拳，我当年第一次做这道题的加强版时，就是先栽在 int 溢出，再栽在滚动更新顺序上，最后才真正理解状态转移。

5. 从 Candy S 延伸出去：这道题教给我们的刷题方法

5.1 一个模型串起来的同类题

Candy S 并不是孤例。把“糖果盒”换成“房屋”、“背包”换成“金币”，你会看到一批题目内核完全一样：一排物品，每个物品有权值，两个位置不能同时选，求最大权值和。理解和记住这个模型，比背具体代码重要得多。我在刷到类似题目时，会先在草稿纸上写出四个要素：物品编号、决策集合、约束条件、状态边界。四个要素都写清楚了，代码写出来基本不会有大改动。

从 Candy S 还可以延伸出带环、带负权、带 K 次限制等变种。比如限制最多只能选 K 个盒子，就要加一维 dp[i][j] 表示前 i 个里选 j 个，复杂度变成 O(NK)；如果把相邻不能选的限制放宽成不能连续选 K 个，状态就要记录最近连续选了几个。这些都是同一个原始模型在不同约束下自然生出的版本，掌握好基础模型以后，扩展题就不再是从零开始。这个“一题多问”的思考方式，才是刷题打卡最大的收获。

5.2 打卡刷题时的复盘方法

既然你是打卡刷题，我更建议每道题都记录两层东西：外层是“这道题的题面特征”，内层是“这道题背后的状态模型”。比如 Candy S，外层特征是糖果、盒子、相邻互斥；内层模型是线性 DP。下次你看到“路灯照明不能相邻”“教室座位不能挨着”“农场作物不能连续种”，第一反应就能类比到同一个模型。复盘时不要只贴代码，要写清楚自己第一版错在哪个地方，为什么当时会想到错误方向。对打卡连续性来说，输出比输入重要得多。

我自己的打卡笔记会包含三个固定栏目：第一栏写题目名称和核心模型，一句话说清楚它是什么；第二栏写初版错误，把 WA 的数据缩到最小规模，贴在手边；第三栏写这次学到的通用技巧，哪怕只是一个“下次初始化先想负数”的提醒。一个月下来，你会发现这些笔记比单纯的提交记录有价值得多。竞赛能力的增长从来不是靠题量堆出来的，而是靠对每一道经典题的深度挖掘。

5.3 C++ 提交前的小习惯

最后是几个野路子经验。第一，USACO 老题在洛谷等 OJ 上可能有文件名重定向，有些古早题目要求从文件读入，现在大多已经改成标准输入输出，但你提交前还是看一眼题面。第二，代码最开头加两行同步关闭，大多数选手已经习惯，但没有这两行在某些测试点上不会错，只是慢；把这两行背下来省心。第三，养成编译器警告全开的口子，本地编译时用 -Wall -Wextra，很多“把变量名写错”的问题在编译阶段就能抓住，不要在 OJ 上交了四五次才发现是一个拼写错误。

还有一个小技巧，我建议每个用 C++ 刷题的人都要掌握：在本地写一个随机数据生成器，专门用来生成小规模样例。拿 Candy S 举例子，你可以写一个生成 n 从 1 到 8 的随机序列的程序，再写一个暴力枚举版本和 DP 版本对拍。对拍没问题之后再提交，正确率会高很多。USACO 系的题目很多都是“思路简单、坑点隐蔽”，对拍是性价比最高的排错手段。

这道题我前后刷了两遍，第一遍只顾着交答案，第二遍才把环形变体和滚动数组彻底想明白。后来再遇到，我发现自己不需要重新推方程，脑子里会有非常清晰的一条线：局部决策影响范围多大，就决定状态维度需要往哪个方向延伸。如果你跟我一样是每天固定刷几道题提升手感，建议别只满足于 AC，把每个版本的边界都亲手跑一遍，再用随机数据对拍一下，那才是银牌题真正留给你的东西。Candy S 这道题代码量很小，但每次回看都能让我对动态规划的理解更扎实一点。