今天打卡的是洛谷 P5424USACO 2019 Open Contest 的 Gold 组第一题原题名就叫Snakes题号标记为 [USACO19OPEN] Snakes G。别看题目叫“Snakes”就以为是贪吃蛇模拟实际上这是一道非常典型的序列分段 DP也是我最近刷信奥题时觉得“翻译难懂、模型一出来就简单”的代表题目。这道题的适用范围很明确你在准备 USACO Silver/Gold或者正在练 C 动态规划尤其是那种“给一个序列最多切 K 刀每一段的代价怎么怎么算”的模型那么这道题值得你仔细啃一遍。N 只有 400K 最大也只有 NO(N²K) 的做法规规矩矩就能过完全不需要什么高级优化。下面我按自己从读题到 AC 的完整顺序来讲包括题意分析、状态设计、完整 C 代码以及我实际提交时踩过的几个边界坑。1. 题目到底在说啥一排蛇、一张网、有限的换网次数1.1 先把英文题意“翻译”成人话有 N 组蛇按顺序排成一排第 i 组里有 a[i] 条蛇。农夫要从第 1 组开始一组一组地捕蛇。捕蛇的时候要用网网有一个“容量”这个容量必须大于等于当前这一组蛇的数量否则装不下。每组捕完之后农夫可以选择“换网”也就是把当前网丢掉重新设置一个任意大小的新网。但是换网次数有限制最多只能换 K 次。如果没有换网次数限制答案显然就是 0——每一组都用一个刚刚好等于该组蛇数的网一点浪费都没有。有了 K 的限制题目才有意思。什么叫“浪费”如果当前网的容量是 C这一组实际有 x 条蛇那么浪费就是 C - x。注意网容量是你选择的你可以选得比实际蛇数大很多但那样浪费就多你也可以选得刚刚好但你可能没有那么多换网次数。最终目标在不超过 K 次换网的前提下把所有蛇捕完使得总浪费最小。输入格式第一行两个整数 N, K表示有 N 组蛇最多换 K 次网。第二行 N 个整数a[1] 到 a[N]。输出一个整数表示最小总浪费。1.2 两个“想当然”的策略为什么都不行我第一次读这题时脑子里立刻冒出两个贪心方案方案一每组的网容量都刚好等于这一组的蛇数这样单组浪费永远是 0。但代价是每组之间理论上都需要换一次网如果 N 组全部分开需要换 N-1 次。K 通常小于 N-1所以这个方案只适合 K 非常大的情况。方案二从头到尾只用一张最大的网容量等于所有组蛇数的最大值。这样一次网都不用换但除了那一组本身其它每一组都在浪费。假如数据是 [3, 1, 2, 5]一张大网容量 5浪费就是 (5-3)(5-1)(5-2)(5-5) 9非常难看。真正的最优解一定是上面两个方案的某种折中把序列切成若干个连续的块每块共用一张网。每张网的容量选成这一块里的最大值这样既能保证装得下又不会选择一个更大的、白白浪费的容量。1.3 题眼把“换网次数”翻译成“序列分段”这一步是整个题目的核心转化。假设我们已经决定用 t 张网那么这 t 张网覆盖的范围必然是 N 组蛇划分成的 t 个连续区间。换网次数 K 和段数 t 的关系是如果题目允许的 K 是指“额外再设置 K 次网”那么第一次买网/设网不算换网次数所以总段数最多是 K1。如果 K 是指“总共能设置 K 张网”那么段数最多就是 K。USACO 官方英文描述是 Farmer John 可以“reset the net at most K times”也就是说第一次把网架起来不算 reset所以惯例题解里段数上限是 K1。洛谷 P5424 也遵循这个语义后面我会专门再讲这里容易踩的坑。于是问题变成了一个纯模型给定一个长度为 N 的数组 a把它分成不超过 K1 个连续段每一段 [l, r] 的代价 cost(l, r) 段长 × 段内最大值 - 段内所有元素之和。求所有段代价之和的最小值。为什么每段代价是“段长 × 段内最大值 - 段和”因为这一整段共用同一张网网的容量只能选这段的最大值那么这一段的浪费就是每一组的“容量 - 实际蛇数”累加(max - a[l]) (max - a[l1]) ... (max - a[r]) 段长 × max - (a[l] ... a[r])这个公式必须刻在脑子里它直接决定了后面预处理要做什么。2. 状态设计和转移方程先想清楚“最后一段”2.1 为什么状态里必须带“用了几张网”如果没有段数限制答案为零问题没意义。所以 DP 状态第一维必须是“处理到第几组”第二维必须是“用了多少张网”。用网数就是段数。定义 dp[i][j]前 i 组蛇用了 j 张网也就是把前 i 组分成了 j 段时能得到的最小总浪费。这里有个小细节值得说明dp[i][j] 表示的是“恰好用了 j 张网”还是“最多用了 j 张网”我习惯定义成“恰好”最后在答案里对所有合法的 j 取 min。因为“最多 K1 段”并不要求你必须用完这么多段比如 K 很大但数据本身就单调可能分两段就已经最优了所以最终答案是 min(dp[N][1], ..., dp[N][K1])而不是只取 dp[N][K1]。初始条件dp[0][0] 0前 0 组用了 0 张网浪费为 0。dp[i][0] INFi 0 时不合法。dp[0][j] INFj 0 时不合法。其它所有 dp[i][j] 初始为 INF。2.2 转移方程枚举最后一张网覆盖了哪些组这是分段 DP 最标准的思考方式不考虑前 i 组到底怎么分的只看最后一张网覆盖的区间是 [p1, i]。前 p 组一定用掉了 j-1 张网它们内部的最优代价是 dp[p][j-1]。最后一段 [p1, i] 共用一张容量为 max(a[p1..i]) 的网代价是 cost(p1, i)。所以dp[i][j] min( dp[p][j-1] cost(p1, i) )其中 p 从 j-1 枚举到 i-1为什么 p 至少从 j-1 开始因为前 j-1 张网至少要覆盖 j-1 组蛇一组蛇至少占一个位置所以 p 不能小于 j-1。这是一个很实用的剪枝也能帮助理解状态的合法性。这个转移为什么是对的因为最后一段的起点是 p1不管前面 p 组怎么切分都不会影响最后一段的代价满足无后效性。我们枚举所有可能的 p就能覆盖所有可能的“最后一段”划分方式。2.3 cost(l, r) 必须先预处理出来如果每次转移都现场扫一遍 [p1, i] 求最大值和区间和那复杂度就是 O(N³K)N400 时接近 1e10肯定会超时。所以要把每个区间的 cost 提前算好存在一个二维表里。这一点和“区间 DP”很像先把小区间的代价算清楚再用来做大规模转移。需要预处理的只有三样东西区间和 sum(l, r)用前缀和 O(1) 求。区间最大值 max(l, r)N 只有 400直接 O(N²) 暴力预处理最省事。区间代价 cost(l, r) (r - l 1) * max(l, r) - sum(l, r)。后面代码里我会把这三样一次性算出来。2.4 手推一个小样例为什么答案是 3 而不是 9用样例 [3, 1, 2, 5]N4K1。因为 K1最多换 1 次网也就是最多用 2 张网。先算只用一个网的情况容量选全段最大值 5花费 (5-3)(5-1)(5-2)(5-5) 2430 9。这对应 dp[4][1] cost(1,4) 9。再看分成两段的所有可能切法第一段 [1,1]第二段 [2,4]cost(1,1) 0cost(2,4) 中最大值 5段长 3段和 1258花费 15-87。总花费 7。第一段 [1,2]第二段 [3,4]cost(1,2) 23-42cost(3,4) 25-73。总花费 5。第一段 [1,3]第二段 [4,4]cost(1,3) 3*3-63cost(4,4)0。总花费 3。所以最优切法是前 3 组用一张容量 3 的网最后一组单独用容量 5 的网总浪费 3。注意这里换网次数正好是 1 次先设一张 3 的网捕完第 3 组后换成 5 的网捕第 4 组完全符合 K1 的限制。这个样例手算完DP 的每个变量就都清晰了dp[4][2] min(dp[0][1] cost(1,4), dp[1][1] cost(2,4), dp[2][1] cost(3,4), dp[3][1] cost(4,4))。其中 dp[3][1] cost(1,3) 3加上 cost(4,4)0得到 3。3. 三样预处理 完整 C 实现3.1 前缀和、区间最大值和成本表的预处理顺序代码里我统一用 1 起始下标方便写前缀和和区间边界。第一步读入数组 a[1..N]做前缀和 pref[i]表示前 i 组蛇的总数。区间 [l, r] 的和就是 pref[r] - pref[l-1]。第二步处理区间最大值 mx[l][r]。因为 N 最多 400我用一个很朴素的双重循环固定左端点 l然后右端点 r 从 l 往右扫用一个临时变量 curMax 维护当前看到的最大值。这样每个区间的最大值都能存下来复杂度 O(N²)约 16 万次完全可以忽略。第三步直接顺手把 cost[l][r] 也填了cost[l][r] (r - l 1) * curMax - (pref[r] - pref[l-1])。因为在这个循环里 curMax 就是 mx[l][r]。这里有个小技巧cost 表不一定必须单独开一个二维数组你可以在 DP 转移时用 mx 和前缀和现场算。但单独存下来有个好处代码阅读起来更清晰而且 O(N²) 的内存也只有 400×400 的 long long约 1.3MB完全无所谓。我一直认为信奥代码里“为了省一个数组把逻辑搞得一团乱”是最不划算的事。3.2 完整可提交代码下面直接给出完整 C 代码。默认是洛谷提交方式也就是标准输入输出。如果你要交 USACO 官方的 snakes.in / snakes.out把代码里注释掉的那两行 freopen 打开即可。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 如果是在 USACO 官方评测打开下面的文件重定向 // freopen(snakes.in, r, stdin); // freopen(snakes.out, w, stdout); int N, K; cin N K; vectorlong long a(N 1, 0); for (int i 1; i N; i) cin a[i]; const long long INF (1LL 60); // 前缀和用于 O(1) 求区间和 vectorlong long pref(N 1, 0); for (int i 1; i N; i) pref[i] pref[i - 1] a[i]; // mx[l][r] 和 cost[l][r]O(N^2) 预处理 vectorvectorlong long mx(N 1, vectorlong long(N 1, 0)); vectorvectorlong long cost(N 1, vectorlong long(N 1, 0)); for (int l 1; l N; l) { long long curMax 0; for (int r l; r N; r) { curMax max(curMax, a[r]); mx[l][r] curMax; int len r - l 1; cost[l][r] 1LL * len * curMax - (pref[r] - pref[l - 1]); } } // 关键K 次换网 最多 K1 个连续段 // 但段数不可能超过 N所以取 min避免无意义的大数组 int maxSeg min(K 1, N); // dp[i][j]前 i 组蛇分成 j 段用了 j 张网的最小浪费 vectorvectorlong long dp(N 1, vectorlong long(maxSeg 1, INF)); dp[0][0] 0; for (int j 1; j maxSeg; j) { // i 至少要有 j 组才能分成 j 段 for (int i j; i N; i) { // p 是前 j-1 段覆盖的组数p 至少要等于 j-1 for (int p j - 1; p i; p) { if (dp[p][j - 1] INF) continue; long long cand dp[p][j - 1] cost[p 1][i]; if (cand dp[i][j]) dp[i][j] cand; } } } long long ans INF; for (int j 1; j maxSeg; j) { ans min(ans, dp[N][j]); } cout ans \n; return 0; }这个代码直接抄就能过洛谷 P5424。几个细节我解释一下所有跟数量有关的变量都用 long long因为单组蛇数可能到 1e9区间长度最大 400cost 最大可能到 4e11累加后超过 int 范围。INF 用了 (1LL 60)也就是大约 1.15e18足够大而且保证加一个 cost 不会溢出到负数。不要用 0x3f3f3f3f那是 int 时代的习惯放到 long long 场景太小了。maxSeg 取了 min(K1, N)。如果 K 很大比如 K N-1maxSeg 就等于 N答案一定为 0因为每个组都可以单独用一张网如果不加这个 min当 K 特别大时数组会多开一些无意义的行虽然不影响正确性但不是好习惯。最内层循环里p 从 j-1 开始而不是从 0 开始。不仅节省了无效计算还保证了“前 j-1 段覆盖 p 个位置”的合法性。3.3 复杂度分析为什么 N400 这么宽松预处理部分前缀和 O(N)区间最大值和 cost 表 O(N²)。DP 部分枚举 j 从 1 到 maxSegi 从 j 到 Np 从 j-1 到 i-1。总计算量大约是 N × maxSeg × N写成 O(N²K)。N400K400最坏情况下大约 6400 万次内层操作每次都是几个 long long 的加法和比较现代评测机上 1 秒内轻松跑完USACO 给这道 Gold 题的时间限制是 2 秒所以没有任何压力。内存部分mx 和 cost 各是 401×401 的 long long 数组大约 2.6MBdp 更小整体不超过 10MB。这个数据范围就是不让你想太多老老实实暴力预处理 三重循环就是最优解。4. 实测踩坑边界、初始化、换网次数定义这部分是我实际提交时最容易出问题的地方也是很多同学看了题解还 WA 半天找不到原因的地方。4.1 最大的坑K 到底代表几张“新网”我在前面反复强调过USACO 原题里的 K 是“reset the net at most K times”所以第一次架网不算 reset因此最多可以设置 K1 张不同的网。洛谷上的题目描述基本沿用了这个意思所以正确做法是段数上限 K1。但是有一批中文题解或者其它 OJ 上的翻译会把 K 描述成“最多买 K 张网”那这时候段数上限就应该是 K 而不是 K1。如果你按 K1 写遇到某些平台的加强数据答案可能会偏小如果按 K 写而题目其实是 K1 的语义答案又会偏大。所以看到题面第一件事就是确认样例里的换网次数语义。怎么确认最简单的方法就是拿 K1 的样例去算。像 [3, 1, 2, 5] 这个数据如果按“最多用 2 张网”理解答案是 3如果按“总共只能用 1 张网”理解答案是 9。所以只要你把样例算一遍就能立刻判断出题人用的是哪种语义比死记公式可靠。4.2 N1、K0、K≥N 这些极端情况N1 时只有一组蛇不管 K 是多少答案都是 0因为只要设一张容量等于 a[1] 的网就行。上面的代码里maxSeg min(K1, N) 1dp[1][1] cost[1][1] 1 * a[1] - a[1] 0输出 0正确。K0 时一次网都不能换全程只有一张网答案就是 cost[1][N]也就是容量取全段最大值的总浪费。代码里 maxSeg min(1, N) 1答案取 dp[N][1]正确。K 非常大比如 K N 甚至更大时理论上可以做到每组单独一张网总浪费 0。代码里 maxSeg 被 min 到 Ndp[N][N] 0ans 最小值也是 0正确。4.3 long long 和 INF 的隐蔽问题这题的数据范围表面上 N 很小容易让人放松警惕。我第一次写的时候用的是 int结果样例过了自己构造的大数据直接溢出成负数wa 得莫名其妙。单组蛇数上限是 1e9段长最大 400一个区间的 cost 就是 400 × 1e9 4e11四个区段加起来就是 1.6e12int 最多 21 亿远远不够。INF 的选取也有讲究。如果你用 0x3f3f3f3f也就是 1061109567这个值在 int 里看起来很“无穷”但在 long long 的世界里它根本不够大dp[p][j-1] cost 可能超过它导致你以为某个状态不可达实际却是可以达到的。我建议统一用 (1LL 60)这是信奥代码里最稳妥的“大数”。4.4 洛谷和 USACO 官方评测的文件差异洛谷提交直接用标准输入输出但 USACO 官方要求从 snakes.in 读、往 snakes.out 写。我做 USACO 训练时习惯写一个开关式文件重定向// #define USACO_LOCAL #ifdef USACO_LOCAL freopen(snakes.in, r, stdin); freopen(snakes.out, w, stdout); #endif平时在洛谷或者自己电脑上测试时注释掉提交 USACO 时打开。这种小习惯能避免很多因为忘记删 freopen 而导致的本地 Run Error。4.5 一组可以直接用来验证的测试数据下面这组数据我自己提交前会挨个跑一遍确认边界都处理了输入1 4 1 3 1 2 5 输出1 3 输入2 4 2 3 1 2 5 输出2 1 输入3 4 0 3 1 2 5 输出3 9 输入4 1 5 100 输出4 0 输入5 5 2 1 1 1 1 1 输出5 0输入 2 的答案是 1怎么来的分成三段 [3] | [1,2] | [5]三张网容量分别是 3、2、5浪费分别是 0、1、0总共 1。换网次数是 2 次刚好用完。如果你按 K 段而不是 K1 段算这道输入就会得到错误答案所以它是检验“换网次数语义”的绝佳用例。5. 从 Snakes 看一类“序列分段型 DP”5.1 三个识别信号做完这题之后你会发现它的模型非常通用。以后再遇到新题如果同时满足下面三个信号我建议优先往“序列分段 DP”方向想第一题目里有“不超过 K 次 / 恰好 K 次操作”的描述而这个操作是作用在一个连续区间上的。比如“换网”“换颜色”“切换模式”等等。第二区间的代价只和这个区间本身的某些统计量有关。比如最大值、最小值、区间和、区间内不同元素个数并且这些统计量可以在预处理后 O(1) 得到。第三N 不算太大通常在 300 到 5000 之间使得 O(N²K) 的复杂度可以承受。只要这三个信号齐了状态定义几乎可以“抄”dp[i][j]前 i 个元素使用了 j 个“段”的最优值。转移也几乎是定式dp[i][j] min( dp[p][j-1] cost(p1, i) )5.2 什么时候需要进一步优化Snakes 这题 N400所以 O(N²K) 很舒服。但如果哪天你在别的题目里遇到 N2000、K2000这个复杂度就到 8e9 了必须优化。常见方向有两个一是用滚动数组把“段数”这一维滚掉。因为转移只用到 j-1 那一层所以可以把 dp 数组压成两行内存从 O(NK) 降到 O(N)。但注意滚动数组压不掉计算量时间复杂度还是 O(N²K)。二是如果有四边形不等式等决策单调性可以用决策单调优化把枚举 p 的 O(N) 降成 O(logN) 或均摊 O(1)。Snakes 的 cost 函数其实是满足四边形不等式的理论上有优化空间但题目数据范围根本不需要刻意去写反而容易写错、浪费时间。竞赛里“能过题的算法才是好算法”没必要为了炫技增加风险。5.3 和几道经典题的横向对比这类“分段 DP”其实贯穿了整个信奥。比如经典的数字分组问题给你一个数字串要插入 K 个乘号使乘积最大。数字串分成 K1 段dp[i][j] 表示前 i 位分成 j 段的最大乘积转移时枚举最后一段的起点。这和 Snakes 的思考路径完全一致只是 cost 变成了“一段数字拼成的整数”。再比如“最小 m 段和问题”要把数组分成 m 段使所有段的和的最大值最小。虽然这道题通常用二分答案 贪心更简单但用 DP 也能做状态同样是 dp[i][j]转移时枚举最后一段的起点去看这段和是否超过当前二分出的限制。还有邮局问题在数轴上有一排村庄要建 K 个邮局每个村庄由最近的邮局服务求最小总距离。它也是把村庄序列分成 K 段每段由一个邮局覆盖每段代价是村庄到邮局的距离之和。虽然它的代价计算更复杂但大的框架还是那三行转移。所以我把这题当作“分段 DP 家庭”的入门钥匙。你把 Snakes 吃透之后再遇到这类题目至少能快速定出状态和转移不会看到“分成 K 段”就发怵。最后说一个我做这题时的真实体会第一次提交我 WA 得很冤不是因为 DP 写错而是因为我把 K 当成了“总共能用的网数”代码写成了段数上限 K结果样例 K2 的那组数据死活不对。后来我拿样例手算了一遍才意识到 USACO 英文里那句“reset at most K times”说的其实是“重置次数”第一次架网不计入。这个“段数 次数 1”的坑比 DP 转移本身更值得记住。如果你也在这个语义上卡过建议以后拿到任何“K 次操作”的题都先用小样例把“次数到底对应几段”确认清楚再开始写代码。