今天是信奥打卡第 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 位置做出了“不拿”的决策并不代表 i1 就一定要拿它也可以继续不拿。真正的决策点是“当前位置拿还是不拿”而一旦决定拿就压缩了下一个位置的决策空间。这个模型看起来特别像“发糖模拟”但本质上是典型的互补约束选择问题。决策只影响相邻位置这类结构是动态规划最容易处理的形态之一。很多人卡在这一题不是因为不会写代码而是因为一开始把它当成纯模拟题没有意识到自己面对的是一个带约束的最优化问题。1.2 为什么贪心和暴力都容易翻车先看贪心。很多人第一版会写成把 val 复制一份按降序排从头到尾能拿就拿。这个思路在一半的随机数据上看起来都对但只要出现一堆特别大的数聚集在相邻位置贪心就会先拿走其中最大的那个然后导致旁边同样很大的数全部不能拿总收益反而偏低。拿一个具体小例子来说盒子序列是 5, 4, 5如果贪心先取中间的 4两边都废了最后只能得 4但要是不取中间取两边的 5 和 5总和是 10。这一组数据就能把贪心打回原形。再看暴力。如果枚举所有拿取方案每个盒子有拿和不拿两种状态整体时间复杂度是 O(2^N)。银牌题不会给你太小的 N一旦 N 到一万这种指数级搜索连第一个测试点都过不去。中间可能碰到的剪枝技巧可以延长一点寿命但无法解决本质问题。那么动态规划为什么能用在这儿因为它把“从 1 到 i 的最优解”作为子问题而且 i 位置拿不拿只影响 i1 位置的可用性不会影响更远的位置。这种局部影响、整体最优的结构正是 DP 的用武之地。你不需要知道前 i 个盒子具体怎么拿的你只需要知道它们能带来的最大收益是多少这就是 DP 状态设计的核心思想丢掉过程细节只保留与未来决策相关的信息。1.3 三种模型的横向对比方案思路时间复杂度适用性贪心每次取全局最大且未冲突的盒子排序或堆 O(N log N)只在数据特征特别理想时成立相邻聚集时直接崩暴力搜索枚举所有选取集合O(2^N)N 稍微变大就派不上用场只能过最小点动态规划按位置递推当前最优O(N)完全匹配题目结构稳定且容易扩展这个表格不是让你记住结论而是帮你建立“拿到一个优化问题先判断决策影响范围”的习惯。决策只影响固定近邻时优先想到线性 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; vectorlong 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; } vectorlong 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 实现从能过样例到稳稳 AC3.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; vectorlong 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 初始化为 0cur 初始化为第一个盒子能带来的最优值。为什么要初始成 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 vectorlong 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[i] dp[i-1] val[i]忽略了相邻互斥改成 dp[i] max(dp[i-1], dp[i-2] val[i])输出一直偏小初始化时把 dp[0] 设成负数初始化为 0小数据对大数据错int 溢出全部换成 long long循环前后结果错乱滚动数组更新顺序不对用 oldPre / oldCur 重命名或开完整数组验证环形数据全错没有区分首尾两个 case拆成两个区间分别 DP取最大值输入读取异常没有处理 n0 或文件末尾用 if (!(cin n)) return 0; 兜底这张表当然不能覆盖所有问题但它是我复盘这道题时真实遇到过的五个类型。你可以把它当作自检清单在提交之前逐条过一眼很多隐藏问题会提前暴露。尤其是前三条几乎是所有 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 这道题代码量很小但每次回看都能让我对动态规划的理解更扎实一点。 
长河君 · 2026/10/22 16:27:42 · 阅读 1.2k USACO Candy S 题解：线性DP与滚动数组的完美示范
今天是信奥打卡第 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 位置做出了“不拿”的决策并不代表 i1 就一定要拿它也可以继续不拿。真正的决策点是“当前位置拿还是不拿”而一旦决定拿就压缩了下一个位置的决策空间。这个模型看起来特别像“发糖模拟”但本质上是典型的互补约束选择问题。决策只影响相邻位置这类结构是动态规划最容易处理的形态之一。很多人卡在这一题不是因为不会写代码而是因为一开始把它当成纯模拟题没有意识到自己面对的是一个带约束的最优化问题。1.2 为什么贪心和暴力都容易翻车先看贪心。很多人第一版会写成把 val 复制一份按降序排从头到尾能拿就拿。这个思路在一半的随机数据上看起来都对但只要出现一堆特别大的数聚集在相邻位置贪心就会先拿走其中最大的那个然后导致旁边同样很大的数全部不能拿总收益反而偏低。拿一个具体小例子来说盒子序列是 5, 4, 5如果贪心先取中间的 4两边都废了最后只能得 4但要是不取中间取两边的 5 和 5总和是 10。这一组数据就能把贪心打回原形。再看暴力。如果枚举所有拿取方案每个盒子有拿和不拿两种状态整体时间复杂度是 O(2^N)。银牌题不会给你太小的 N一旦 N 到一万这种指数级搜索连第一个测试点都过不去。中间可能碰到的剪枝技巧可以延长一点寿命但无法解决本质问题。那么动态规划为什么能用在这儿因为它把“从 1 到 i 的最优解”作为子问题而且 i 位置拿不拿只影响 i1 位置的可用性不会影响更远的位置。这种局部影响、整体最优的结构正是 DP 的用武之地。你不需要知道前 i 个盒子具体怎么拿的你只需要知道它们能带来的最大收益是多少这就是 DP 状态设计的核心思想丢掉过程细节只保留与未来决策相关的信息。1.3 三种模型的横向对比方案思路时间复杂度适用性贪心每次取全局最大且未冲突的盒子排序或堆 O(N log N)只在数据特征特别理想时成立相邻聚集时直接崩暴力搜索枚举所有选取集合O(2^N)N 稍微变大就派不上用场只能过最小点动态规划按位置递推当前最优O(N)完全匹配题目结构稳定且容易扩展这个表格不是让你记住结论而是帮你建立“拿到一个优化问题先判断决策影响范围”的习惯。决策只影响固定近邻时优先想到线性 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; vectorlong 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; } vectorlong 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 实现从能过样例到稳稳 AC3.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; vectorlong 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 初始化为 0cur 初始化为第一个盒子能带来的最优值。为什么要初始成 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 vectorlong 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[i] dp[i-1] val[i]忽略了相邻互斥改成 dp[i] max(dp[i-1], dp[i-2] val[i])输出一直偏小初始化时把 dp[0] 设成负数初始化为 0小数据对大数据错int 溢出全部换成 long long循环前后结果错乱滚动数组更新顺序不对用 oldPre / oldCur 重命名或开完整数组验证环形数据全错没有区分首尾两个 case拆成两个区间分别 DP取最大值输入读取异常没有处理 n0 或文件末尾用 if (!(cin n)) return 0; 兜底这张表当然不能覆盖所有问题但它是我复盘这道题时真实遇到过的五个类型。你可以把它当作自检清单在提交之前逐条过一眼很多隐藏问题会提前暴露。尤其是前三条几乎是所有 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 这道题代码量很小但每次回看都能让我对动态规划的理解更扎实一点。