★ FEATURED ARTICLE 打卡信奥刷题2907今天要拆解的是 P5424 [USACO19OPEN] Snakes G。这道题我印象很深因为它表面上说的是农夫用网抓蛇网不够大就要扩大最多只能扩 K 次看起来像模拟像贪心但真正做起来会发现这是一道非常地道的区间划分 DP。哪怕你已经学过背包 DP、线性 DP第一次见到这种把序列切分成若干段每段代价由段内最大值决定的模型也容易卡住。这篇文章我会从题意还原开始把抓蛇过程翻译成数学模型然后一步一步推导状态和转移给出完整可提交的 C 代码最后把我自己调试时踩过的坑和暴力对拍方法都交代一遍。无论你是刚开始刷 USACO 的新手还是想在区间 DP 上再夯实一下的老手都应该能从中拿到一点可以直接用的东西。1. 读题先别急着写代码把抓蛇过程翻译成数学模型1.1 题目到底在说什么原题描述的场面是这样的有 N 组蛇第 i 组蛇的数量是 a_i。农夫手里有一个网网的大小可以随意调整。一开始农夫可以自由指定网的大小然后按顺序去抓每一组蛇。抓某一组蛇时如果当前网的大小小于这组蛇的数量那必须先扩大网扩到至少等于这组蛇的数量如果当前网的大小已经够了就不用动。整个抓蛇过程中农夫一共最多可以调整 K 次网的大小。注意题目算的不是扩大网的成本而是每一组都会产生一个浪费值浪费值 抓这组蛇时网的大小 - 这组蛇的实际数量。也就是说网比蛇大得越多浪费越严重正好等于数量则浪费 0。目标是在最多调整 K 次的前提下让 N 组蛇产生的浪费总和最小。我第一次读这题的时候满脑子都是模拟模拟模拟维护一个当前网大小遇到更大的蛇就扩扩的次数用完了就硬扛。后来仔细想想这个思路根本不成立因为你不知道一开始网该设多大也不知道该在哪个位置提前调整更不知道调整的目标值到底应该设为多少。网设小了遇到大蛇被迫扩大一次机会就没了网设大了后面每一组小蛇都在白白浪费。这已经是一个需要全局决策的资源分配问题不是靠局部贪心能解决的。1.2 一组网宽等于一段区间浪费可以公式化我们换个角度看这个问题在相邻两次调整之间网的大小是固定不变的。假设从第 L 组蛇开始一直到第 R 组蛇中间一直没有调整过网那么这段时间网的大小至少要大于等于第 L 到第 R 组里最大的蛇数否则中间就会卡壳被迫调整那就不属于中间没调整过的情况了。既然网只要大于等于段内最大值就行那为了减少浪费最优做法肯定是把它正好设置成这段的最大值 M。为什么如果设置成比 M 更大的值每一组蛇的浪费都会凭空增加没有任何好处。所以每一段内部的网宽可以唯一确定就是段内最大值。这样一来第 L 到第 R 组的浪费总和就可以直接写成公式浪费(L, R) (R - L 1) * max(a[L..R]) - (a[L] a[L1] ... a[R])这个公式的含义很简单这段里每组蛇都按最大值来算浪费但实际只有最大那组蛇是刚好匹配的其余组都比最大值少少的那些就是浪费。整段浪费等于段长乘以段内最大值减去段内蛇数之和。于是题目就转化成了一个纯数学问题把 1 到 N 这个序列切成若干个连续段每段的代价按上面的公式计算要求所有段代价之和最小。至于最多能切多少段取决于调整次数 K一开始设置网的大小算作第一段之后每调整一次网就开启新的一段。所以最多能分的段数是 K 1段数不能再多因为再多就没有调整次数来支撑了。这个转化是整个题目的灵魂。我打一个比方你有一堆长短不一的木棍手里有几把固定长度的尺子量完一段换一把尺子尺子的长度必须不小于这段里最长的那根。你当然希望每把尺子都刚刚好等于这一段中最长那根的长度否则就是浪费。于是问题从有状态的模拟彻底变成了怎么切段最划算这才是 DP 该进场的地方。1.3 为什么贪心救不了这题很多同学看到最多调整 K 次的第一反应是贪心先让网保持尽量小遇到更大的蛇再被迫扩大。这个策略在部分数据上能出正确答案但它有一个致命盲区——它根本想不到主动把网调小这件事。我举个最简单的例子a [5, 5, 1, 1]K 1。如果采用被动贪心的思路一开始把网设成 5那么前两组蛇浪费都是 0第三组浪费 4第四组浪费 4总浪费 8。但如果你在第一组和第二组抓完之后主动消耗那唯一一次调整机会把网从 5 调成 1那么后面两组蛇的浪费就都是 0总浪费直接变成 0。同样的调整次数不同调整时机和目标值结果天差地别。这个例子说明贪心只想着当前遇到更大蛇时怎么应付却完全没考虑后面遇到小蛇时能不能主动换一个更小的网。网的大小调整不是单向的它可以是双向的而每一次调整的时机、调整后的目标值都会影响之后每一组蛇的浪费。这类总共只有 K 次机会怎么分配最划算的问题最自然的解法就是把 K 记进状态里用 DP 来做。别小看这个思维转变它是从模拟者变成规划者的关键一步。2. DP 设计把调整网宽变成切段计数2.1 状态定义dp[i][j] 到底存什么明确了把序列切成 K1 段这个大方向之后DP 状态就顺理成章了。我定义 dp[i][j] 表示考虑前 i 组蛇已经划分成 j 段也就是已经设置了 j 次网的大小并且第 j 段正好覆盖到第 i 组为止时能得到的最小浪费总和。这里有一个特别容易混淆的点j 到底代表调整了几次还是设置了几次网我强烈建议理解成已经确定了几段因为每一段的开始都需要设置一次网的大小。初始设置算第一段后面每调整一次就新开一段所以一共有 K1 段j 的取值范围就是 1 到 K1。如果你非要把 j 理解成调整次数那么写代码的时候还要时刻记得加一减一非常容易把自己绕晕。按这个定义dp 数组的规模是 (N1) 行、(K2) 列的二维表每一项存一个 long long。为什么要 long long因为 a_i 最大可以到 10^9 这个量级N 最大可以到 400最坏情况下浪费总和能达到 4×10^11 左右int 根本存不下。这是很多第一次写这题的人翻车的第一个地方后面调试部分我还会再强调。状态定义里其实还隐含着一个信息dp[i][j] 只关心第 j 段覆盖到了第 i 组至于第 j 段的网宽是多少并不需要单独存。因为它一定等于第 j 段覆盖区间内的最大值这个值可以通过枚举段的起点算出来。这就是 DP 设计中用转移计算中间信息的典型手法少开一维状态思路反而更清晰。2.2 转移方程枚举最后一段的起点有了状态定义下一步就是写转移。思考的时候不要从开头想而是从结尾想dp[i][j] 这个状态它的最后一段是从哪个位置开始的假设最后一段从 k1 开始一直覆盖到 i那么前面 1 到 k 组一定已经被划分成了 j-1 段对应的最小浪费就是 dp[k][j-1]。而最后这一段自身的代价按照第一节推导的公式等于段长乘以段内最大值减去段内和。于是转移方程可以写成dp[i][j] min( dp[k][j-1] (i - k) * max(a[k1..i]) - (pre[i] - pre[k]) )其中 k 的取值范围是 0 到 i-1。这里 k0 表示前面没有任何组前 0 组划分成 0 段是合法的初始状态对应 dp[0][0] 0而 dp[0][大于0] 都是非法状态要设成无穷大。为了快速计算 (pre[i] - pre[k])我先预处理前缀和 pre[i] a[1] a[2] ... a[i]。而 max(a[k1..i]) 这个区间最大值不能像前缀和那样 O(1) 查询只能提前把任意区间的最大值都算好或者在内层循环里边枚举边维护。为什么转移必须枚举 k因为段内最大值依赖于具体的区间 [k1, i]它不是一个可以拆分、可以累加的量你必须知道最后一段覆盖了哪些数才能算出这一段的最大值和和。这种枚举段起点的写法是区间划分 DP 的标准模板虽然看着有点暴力但它是这类题最可靠的出发点。转移的时间复杂度是 O(N^2 K)。如果 N 和 K 都在 400 以内这个复杂度大概是 400×400×400 的量级C 跑起来非常轻松。如果你看到的数据范围更大比如 N 到了 10^5那就要用单调栈加数据结构优化但那是后话本题用朴素 DP 就足够了。2.3 边界和答案认真数清楚段数初始化方面我把 dp 数组全部填成 INF然后单独设置 dp[0][0] 0。接着按照 i 从 1 到 N、j 从 1 到 K1 的顺序填表。填表的顺序要注意计算 dp[i][j] 时会用到 dp[k][j-1]其中 k i所以只要外层循环从小到大枚举 i内层无论怎么枚举 jdp[k][j-1] 都已经算好了。有一个初学者很容易忽略的点答案不是 dp[N][K1]而是 min(dp[N][1], dp[N][2], ..., dp[N][K1])。为什么因为题目说的是最多调整 K 次不是恰好调整 K 次。如果最优方案根本不需要用满 K 次调整比如所有蛇的数量完全一样那分一段就够了你强行分 K1 段只会得到更大的浪费。所以最后一定要在所有可能的段数里取最小值。另外K 的值可能非常大甚至超过 N-1。但一组蛇最多只能被切成 N 段每段至少包含一组再多就没有意义了。所以我在读入 K 之后会先执行一句 K min(K, N - 1)。这一句既防止了 dp 数组开得过大又避免枚举无意义的段数属于稳妥的健壮性处理。还有一个边界细节需要留意k 可以取 0也就是整段从第 1 组开始。这时候用到的是 dp[0][j-1]。只有当 j-1 0 时这个状态才是合法的 0其余情况 dp[0][j-1] 都是 INF自然不会参与转移。换句话说第一段只能作为整个序列的第一段来设置网宽不能凭空从中间开始这符合直觉。3. C 实现完整代码与关键细节3.1 完整代码写到这里代码其实已经呼之欲出了。下面是我整理出的完整可提交版本注释尽量写得清楚一些方便你对照上面的推导过程看。#include bits/stdc.h using namespace std; typedef long long ll; const ll INF 4e18; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, K; cin N K; vectorll a(N 1), pre(N 1, 0); for (int i 1; i N; i) { cin a[i]; pre[i] pre[i - 1] a[i]; } // 最多只需要 N-1 次调整多余的段数没有意义 K min(K, N - 1); // mx[l][r] 表示区间 [l, r] 的最大值 vectorvectorll mx(N 1, vectorll(N 1, 0)); for (int l 1; l N; l) { ll cur 0; for (int r l; r N; r) { cur max(cur, a[r]); mx[l][r] cur; } } // dp[i][j]前 i 组蛇分成 j 段的最小浪费 vectorvectorll dp(N 1, vectorll(K 2, INF)); dp[0][0] 0; for (int i 1; i N; i) { for (int j 1; j K 1; j) { for (int k 0; k i; k) { if (dp[k][j - 1] INF) continue; ll segCost (i - k) * mx[k 1][i] - (pre[i] - pre[k]); dp[i][j] min(dp[i][j], dp[k][j - 1] segCost); } } } ll ans INF; for (int j 1; j K 1; j) { ans min(ans, dp[N][j]); } cout ans \n; return 0; }这段代码没有用任何奇技淫巧逻辑和推导完全一一对应。你把它交到评测系统里正常数据下应该能顺利通过。如果你担心输入较多前面加了 ios 同步关闭的优化如果环境不支持 bits/stdc.h换成标准的 iostream、vector、algorithm 头文件也一样能跑只是我信奥刷题习惯用这一行万能头省事。3.2 逐块拆解代码先看输入部分。我用 vector 存 a 数组下标从 1 开始这样和前缀和的写法一致避免 0-based 和 1-based 混用时改来改去。pre[i] 表示前 i 组蛇的总数量后面计算段内和的时候 O(1) 就能拿到。mx 数组的预处理是这个实现里比较巧的一块。外层枚举左端点 l内层从 l 往右扫cur 不断更新为当前遇到的最大值。这样一个二重循环下来所有区间的最大值都算好了复杂度 O(N^2)。注意 mx 数组的开法行和列都要 N1因为下标从 1 开始而且转移的时候会取到 mx[k1][i]当 k0 时就是 mx[1][i]下标不会越界。DP 循环部分是整段代码的核心。最外层 i 从小到大递增保证内层用到的 dp[k][j-1] 已经计算完毕。第二层 j 从 1 到 K1代表段数。第三层 k 枚举最后一段的起点减一也就是前面有多少组已经被划分掉了。每次转移先把非法状态跳过去然后计算最后一段的代价用 min 更新 dp[i][j]。关于 INF 的选取我习惯用 4e18。这个值比 long long 的最大值 9.22e18 小一半左右做加法不容易溢出加上任何数都不会超过 9e18同时又能保证远大于真实答案。如果你用 1e9 这种看起来很大的数在 a_i 很大时反而可能不够大导致正确答案被错误舍去。最后的答案统计也值得多说一句。我重新扫了一遍 dp[N][1] 到 dp[N][K1] 取最小值而不是直接输出 dp[N][K1]。这一点在 2.3 已经解释过了但代码里很容易手滑写错。我建议至少在注释里标一句K 是上限不是精确次数。3.3 复杂度分析与空间技巧这份代码的复杂度由两部分组成预处理 mx 数组 O(N^2)DP 转移 O(N^2 K)。内存上mx 数组是 O(N^2)dp 数组是 O(N·K)。在 N 和 K 都是几百的情况下时间和空间都非常充裕。如果你想让空间再省一点其实 mx 也可以不预处理而是在第三层循环里从 i 往左枚举 k同时维护一个从 i 往左看到的最大值。这样每算一个 dp[i][j] 都要重新扫一次复杂度不变但省下了整个 mx 数组。我之所以保留 mx 数组是因为代码更容易对照公式阅读调试的时候也更直观。实际比赛中如果内存紧张用滚动方式维护区间最大值也是一种思路。另外dp 数组的第二维也可以做滚动优化把 j 这一维压成两个一维数组因为转移时只用到了 j-1 这一层。但这样会让代码的可读性下降不少而且本题空间完全够用我建议新手先写二维版本把逻辑跑通再说。做题的第一目标永远是正确其次才是在正确的基础上谈优化。4. 真实调试实录这题我踩过的坑和对拍方法4.1 四个最容易翻车的细节第一个坑就是 int 溢出。我前面提过a_i 可以到 10^9N 可以到 400最坏情况下段内最大值的乘积是 400×10^9 4×10^11前缀和也是同样的量级。用 int 存这些中间结果轻则答案错误重则直接爆成负数。所以这个题从一开始就老老实实用 long long所有的运算都统一用 long long不要 int 和 long long 混着算混着算很容易悄悄溢出。第二个坑是 恰好 K 次 和 最多 K 次 的区别。很多人把这个题想成必须用满 K 次调整于是直接输出 dp[N][K1]。结果面对一组所有蛇数量都相等的测试数据时明明答案应该是 0程序却因为强制分成很多段而输出一个正数。记住这句话上限不是定额最后一定要取最小值。第三个坑是 k 的枚举范围。有些同学写转移时把 k 从 1 开始枚举这样第一段永远无法被正确计算。因为第一段对应 k0意思是前面没有任何组。如果你漏掉 k0dp[i][1] 就会一直保持 INF后续所有状态全部变成 INF整个 DP 表都是废的。这个错误特征非常明显答案会是一个巨大的 4e18看到这种输出第一反应就该检查 k 的起点是不是 0。第四个坑是 K 的处理。如果输入数据里 K 远大于 N你仍然按照 K 去开数组第二维会变得非常大内存和运行时间全部失控。即使侥幸没爆内存枚举那些根本不可能用到的段数也是浪费时间。所以读入后立刻执行 K min(K, N - 1)这是一个性价比极高的防御性写法。4.2 暴力对拍小数据验正确性信奥选手都知道写 DP 题最怕的是样例过了但 WA因为 DP 的状态转移一旦想偏小样例可能完全暴露不出来。我自己的习惯是写一个暴力算法专门用来对拍复杂度怎么慢怎么来只要答案暴力正确就行。对于这题暴力做法很直接枚举所有可能的切段方案。因为最多 K1 段段与段之间是连续切开的所以可以递归枚举每一段的结束位置把所有段的浪费加起来取最小值。我给出一个简单的思路写一个 dfs(pos, segs_left)表示当前从第 pos 组开始还剩 segs_left 段可以切如果 segs_left 等于 1就直接计算 pos 到 N 这一段的浪费并返回否则枚举这一段切到哪个位置 r然后递归处理 r1。这个暴力在 N 比较小的时候比如 N ≤ 12非常快而且思路和 DP 完全不同适合互相验证。对拍的流程是造一组随机小数据分别跑暴力程序和 DP 程序比较输出。如果不一样就把这组数据保存下来逐步调试 DP。我发现用这个方法调试答案取 min(dp[N][1..K1])这个点特别有效因为暴力天然就会尝试不同的段数而如果 DP 只输出最后一列对拍几乎立刻就能发现问题。对拍数据生成时要注意几个边界K 可以取 0表示一次都不能调整a_i 可以全部相等也可以出现极端的大值和小值。这些边界情况恰恰是最容易让 DP 实现暴露问题的点。多造几组每组都让 K 从 0 到 5 随机变化a_i 从 1 到 20 随机取值基本能把所有边界都覆盖到。4.3 极限数据与 long long 检查对拍只能验证逻辑正确性大数据还要靠手工构造检查溢出和性能。我会本地构造一组 N400、K400、所有 a_i10^9 的数据跑一遍看时间和输出。这种数据下所有蛇数量相同答案显然是 0如果输出不是 0说明状态或初始化有问题如果程序运行时间超过几秒说明实现里有不必要的常数。这种极限数据的另一个作用是检验代码在极端内存下的表现。dp 数组开成 (401)×(401)mx 数组开成 (401)×(401)每个元素 8 字节总共大约 2.5MB完全没问题。如果你把 dp 开成 (N1)×(K1) 而遗漏了 K2在某些边界情况下会出现数组越界表现是本地小数据正常、评测大数据神秘 RE。这个我建议直接写在代码注释里提醒自己第二维开 K2 是为了留出下标 K1别省这一格。还有一些编译器层面的小坑。如果你用局部变量存 INF然后在函数里做加法比如 dp[k][j-1] segCost极端情况下两个 4e18 量级的数相加会溢出。我在代码里用 if (dp[k][j-1] INF) continue; 排除非法状态就是为了避免这种无意义的加法。真实答案不可能接近 INF合法状态的 dp 值也不会大到那个程度所以加上这个跳过判断之后能放心大胆地做加法。5. 拿到这题之后我的做题顺序复盘5.1 这类分段 DP还能怎么用做完这道题之后我最大的收获不是会了某个写法而是总结出了一类分段 DP的识别信号题目要求把序列切分成若干连续段段的个数有上限每段的代价只和段内某些统计量最大值、最小值、和等相关且这些统计量不能简单拆分需要枚举段的边界。遇到这种题基本就直接往枚举最后一段的起点这个模板上去靠。类似的变种很多。比如有的题要求每段代价是段内最大值减最小值有的题要求段内所有数互不相同否则代价无穷大还有的题段与段之间有一个额外的限制比如相邻两段的最大值必须保持某种关系。这些都是在转移方程里多加一点条件核心框架仍然是dp[i] min(dp[k] cost(k1, i))。我在做这题时还想到过一个问题如果 N 很大K 也很大O(N²K) 过不了怎么办这时一般有两条路。一条是观察段内最大值只有单调栈预处理的所有支配点处才可能发生变化把内层枚举的 k 压缩到 O(N log N)另一条是如果代价函数满足四边形不等式可以用决策单调性优化。但这些都是进阶话题做信奥题应该先保证朴素写法能过再去想优化。本题的数据范围下老老实实枚举 k 就是最稳的方案。5.2 我的做题习惯总结刷这题让我重新确认了自己的几个做题习惯。第一永远先花五分钟把题目翻译成数学结构。抓蛇、扩网这些生动描述本质上就是切段、求段内最大值、算浪费。把题面剥干净之后再动手代码写起来会顺畅很多也不容易在中途被一堆名词绕晕。我见过不少同学对着题目发呆其实是在脑子里模拟抓蛇过程试图手算出答案这方向就偏了。第二DP 题一定要把边界状态单独拿出来检查。这题的 dp[0][0]0、k 从 0 开始枚举、答案取所有段数的最小值这三个点如果有一个漏掉程序就会在很隐蔽的地方出错。我在对拍时故意把 K 设成 0 跑一遍就是为了确认一次都不能调整的情况也能正确处理。第三代码里凡是涉及 long long 的地方从一开始就用 long long 写不要先用 int 跑通再说。信奥比赛的测评环境通常很严格一个溢出就能让你从 AC 变成 WA而溢出类错误又特别难肉眼发现。与其最后花半小时查 bug不如最开始就统一类型。最后这道题我建议你有空再用滚动数组优化一版不是为了省那几十 KB 内存而是为了练习把状态压掉的思路。当你把 dp 的 j 维度压成两层之后再回头看二维版本会对 DP 的转移顺序有更深的理解。这种能力在做更复杂的优化题时非常有用。先把最朴素的版本吃透再慢慢变强这是我做信奥题最踏实的一条路线。
阅读完成 · 觉得有帮助？
