★ FEATURED ARTICLE USACO 2019 US Open 金牌组的 Snakes对应 OJ 题号 P5424是我刷信奥 DP 时反复回看的一道区间 DP 题。刚拿到题目的时候我以为是个贪心模拟网小了就调大调一次记录一次完事。结果样例都算不对回去把题面又读了三遍才发现真正的问题模型是“把蛇群序列切成若干连续段每段用同一个网的大小去接最小化浪费空间”。搞懂这一步之后代码其实很短核心就是状态设计和几个边界处理。这篇文章我会从题意拆解开始把“为什么是区间 DP”“状态怎么定义”“转移方程怎么来”“C 怎么写”完整过一遍最后整理几个我实际提交时踩过的坑。适合正在刷 USACO Gold、或者准备提高组 DP 专题的选手参考。如果你已经会普通的线性 DP那这道题就是一次很好的思维升级把一个“带次数限制的调整操作”翻译成“分段”。1. 题目在说什么先搞清楚“网”和“浪费”两个概念题目给的场景是这样的农夫约翰有一张网网的尺寸是一个正整数。尺寸为 s 的网能抓住尺寸不超过 s 的蛇。蛇是分成 N 组按顺序出现的第 i 组的蛇大小为 a[i]约翰必须一组一组地抓。关键限制在于约翰最多可以调整网的尺寸 K 次。而且这个次数是包含最开始的展开动作的也就是说“从 0 调成某个值”也算一次调整。如果网的尺寸 s 大于某一组蛇的尺寸 a[i]那多出来的 s - a[i] 就是浪费。举个具体例子网设成 5抓到一组尺寸为 2 的蛇浪费就是 3。目标是让所有组的浪费总和最小。这里有个很容易想歪的地方蛇是一组一组出现的不是一条一条出现的。很多人一开始会把“网尺寸”和“当前最大蛇尺寸”做比较然后一路只调大不调小但题目允许你在任意两组之间把网调大或者调小。调整次数有限所以不可能每一组都用刚好合适的网去抓。生活里有个很贴切的类比你要用几个固定尺寸的盒子去装一堆大小不同的球球按顺序来盒子尺寸可以换但最多只能换 K 次。每换一次盒子你就要把盒子尺寸定下来之后连续装进来的球如果比盒子小空出来的空间就是浪费。题目问的就是怎么安排这 K 次换盒子让浪费最少。样例其实很能说明问题。N 3K 1a [1, 3, 2]。因为只有一次调整机会所以你只能把网设成一个尺寸从头用到尾。为了能抓住所有蛇网至少要设成 3。浪费就是 (3-1) (3-3) (3-2) 3。这个结果告诉我们一件事调整次数越少越倾向于用一个较大的网覆盖全部浪费自然就大。那如果 K 2 呢你可以先设成 1 抓第一组再调整成 3 抓后面两组浪费变成 0 (3-3) (3-2) 1。所以调整次数允许越多越能把大网“精准”地用在大蛇出现的段落上。这其实就是整道题的核心调整次数决定了你能把序列切成多少段。2. 三个关键观察从暴力分段到区间 DP 的思路转变这道题的 N 上限是 400K 上限也是 400。如果不知道模型很容易想到暴力枚举所有换网位置但那是组合数级别的方案数绝对跑不动。想通下面三个观察点问题就清晰了。第一个观察一次调整之后网会维持同一个尺寸连续抓若干组蛇。因为抓完一组你才有机会换网所以换网的位置一定在两组之间。这样一来整个序列就被换网的位置切成了若干个连续的区间段。调整 K 次最多得到 K 段。每一段内网从头到尾保持一个尺寸段与段之间可以不一样。第二个观察在一个确定的区间 [l, r] 内最优的网尺寸一定是这个区间内所有 a 的最大值。道理很直接网设小了抓不住大蛇网设大了只会增加浪费。所以给定区间网的尺寸就被唯一确定了就是区间最大值 M max(a[l..r])。第三个观察给定区间后这段的总浪费可以预先算出来。如果区间长度是 len区间内蛇的尺寸和是 sum那么浪费就是 M * len - sum。因为每一条蛇相对网尺寸 M 浪费 M - a[i]把整个区间的浪费累加起来就是 M 减去每个元素再求和也就是 M * len - sum。有了这三个观察原题就等价于一个非常标准的模型把长度为 N 的序列 a 切成不超过 K 段每一段的代价是“段长 × 段最大值 - 段和”求总代价的最小值。这时候贪心为什么不行的原因也清楚了。贪心通常只盯着“当前最大蛇”去调网但最优解需要考虑两个因素的平衡一是段的长度越长峰值网浪费小蛇越多二是段切得越短需要的调整次数越多。这两个变量互相牵制贪心没办法同时决策分段位置和段内峰值。比如你想把一个很大的峰值留给未来的大蛇那你可能就要忍受当前段内很多小蛇被大网浪费反过来如果你为了减少当前浪费频繁换小网调整次数可能就不够用了。这种 trade-off 只能通过枚举分段点来权衡也就是动态规划。所以这道题虽然表面上是个捕蛇故事本质上是区间划分类的 DP。预处理出所有区间的代价 cost[l][r] 之后剩下的工作就是写一个二维 DP 去枚举最后一段从哪里开始。3. 状态设计与转移方程把“调整次数”翻译成“段数”我用的状态定义是dp[k][i] 表示考虑前 i 组蛇使用不超过 k 次调整包含最开始展开网的那一次时能得到的最小浪费。注意这里的“不超过”三个字很重要。题目说最多 K 次所以允许你实际用掉的次数少于 K。我写代码的时候会让每一层都继承上一层的答案这样就保证 dp 数组里存的一直是“不超过 k 次”而不是“恰好 k 次”。边界条件有两个dp[0][0] 0表示前 0 组蛇、0 次调整浪费为 0。dp[0][i] INFi 0 时表示一次都不展开网当然不可能抓住任何蛇。转移方程是核心。假设最后一段从第 j1 组开始一直延伸到第 i 组。前面这 j 组蛇已经在“不超过 k-1 次调整”的情况下处理完了花费是 dp[k-1][j]。然后最后一段用第 k 次调整把网设成区间 [j1, i] 的最大值这一段的浪费就是预先算好的 cost[j1][i]。所以转移就是dp[k][i] min(dp[k][i], dp[k-1][j] cost[j1][i])其中 j 从 0 取到 i-1。这里 j 可以从 0 开始是因为允许第 1 组就是最后一段的开始点也就是前面没有任何蛇只有一次调整动作。而 dp[k-1][0] 在当前实现里是 0表示允许把前面几次调整“消耗”在空区间上。这看起来很怪但因为最后取的是“不超过 k 次”的最小值多消耗次数不会让答案变好所以不会造成错误。转移里还有一个细节每一层 k 开始时先让 dp[k][i] 继承 dp[k-1][i]。这表示本来最多可以用 k 次但我选择少用一次结果不会更差。这样的话最后答案直接输出 dp[K][N] 就行不需要再对 k 取一遍最小值。时间复杂度很好算状态数是 K × N每个状态要枚举 j 从 0 到 i-1总复杂度 O(N^2 K)。N 和 K 都只有 400最坏情况是 400 × 400 × 400也就是大概 6400 万次运算C 完全没压力。空间上开两个 405 × 405 的二维数组内存也只有几 MB。预处理 cost[l][r] 也需要 O(N^2)。因为 N 很小直接从每个左端点 l 出发向右扫一边维护当前最大值和当前和一边把 cost[l][r] 填进去。不要用 RMQ 或者线段树没必要。4. C 完整实现预处理、DP 循环、边界处理一次讲透下面是我实际提交通过的核心代码。整体思路很直白预处理区间代价然后三层循环跑 DP。#include bits/stdc.h using namespace std; typedef long long ll; const int MAXN 405; const ll INF 4e18; int N, K; ll a[MAXN]; ll cost[MAXN][MAXN]; ll dp[MAXN][MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin N K; for (int i 1; i N; i) { cin a[i]; } // 预处理所有区间的代价 // cost[l][r] max(a[l..r]) * (r - l 1) - sum(a[l..r]) for (int l 1; l N; l) { ll mx 0; ll sum 0; for (int r l; r N; r) { mx max(mx, a[r]); sum a[r]; cost[l][r] mx * (r - l 1) - sum; } } // dp[k][i] 表示前 i 组蛇最多用 k 次调整的最小浪费 for (int i 1; i N; i) { dp[0][i] INF; } dp[0][0] 0; for (int k 1; k K; k) { // 先用 k-1 次调整的结果兜底表示第 k 次可以不用 for (int i 0; i N; i) { dp[k][i] dp[k - 1][i]; } // 枚举最后一段的起点 j1 for (int i 1; i N; i) { for (int j 0; j i; j) { if (dp[k - 1][j] INF) continue; ll val dp[k - 1][j] cost[j 1][i]; if (val dp[k][i]) { dp[k][i] val; } } } } cout dp[K][N] \n; return 0; }代码很短但有几个点必须解释清楚。先说 cost 为什么用 long long。虽然 a[i] 最大只有 10^6但最大值乘区间长度之后可能到 4 × 10^8累加之后更大int 会溢出。dp 数组更是如此最坏情况下一共 N 段每段代价都能到 4 × 10^8总最大值可能超过 10^11所以必须用 long long。INF 设成 4e18 是为了让 INF 加上任何合法值仍然是一个很大的数不会在 min 比较中产生错误结果。再看 dp[0][i] 的初始化。dp[0][0] 0 表示空序列不用任何调整dp[0][i] INF 代表没有一次调整就想去抓前 i 组蛇是不可能的。这个初始化很多人会漏掉漏掉之后 dp[0][i] 默认是 0转移会把非法状态当成 0 去加答案直接错乱。k 层循环里的继承操作也值得多说一句。如果不做继承dp[k][i] 存的只是“恰好用 k 次调整”的最优值那最后就不得不写一个 for 循环从 0 到 K 取最小值。做了继承之后dp[k][i] 天然就是“最多 k 次”的最优值输出 dp[K][N] 即可。这个写法既贴合题意又省去了最后一步取 min。转移的枚举顺序我习惯外层 k中层 i内层 j。这样 dp[k-1][j] 一定已经算好不会出现滚动数组覆盖导致的问题。这里我没有用滚动数组压成一维因为二维数组大小很小写起来更清楚。编译运行之后拿样例 3 1 / 1 3 2 测试程序输出 3和手算一致。把 K 改成 2 再测输出 1。这个对比也能帮助你确认自己理解对了“调整次数包含初始展开”这个设定。5. 常见问题与排查技巧实录这道题看起来简单实际提交时出问题的地方不少。我把自己踩过的坑和一些朋友问过的问题整理成了一张速查表。现象可能原因处理方法答案比预期小很多dp 数组初始化为 0非法状态参与了转移确保 dp[0][1..N] INFdp[0][0] 0答案比预期大忘了做 k 层继承输出的是“恰好 K 次”每层先令 dp[k][i] dp[k-1][i]大样例输出负数或溢出用了 int 存 cost 或 dp全部换成 long longINF 用 4e18样例输出 1但题目期望 3对“初始展开是否算一次调整”理解不一致确认题面若不计初始读入 K 后执行 K运行超时转移枚举了不必要的位置或者用了 O(N^3 K) 写法三层循环已经是 O(N^2 K)400 规模不会超时dp 越界内层循环 j 枚举到了 ij 的范围是 0 到 i-1最大到 i 就错了第一个坑最常见。很多新手看到 dp 是全局变量默认全 0就觉得万事大吉。实际上 dp[0][i] 必须设成 INF否则第一次转移时会把“没展开网就抓了前 i 组蛇”当成合法方案导致答案严重偏小。第二个坑和状态定义直接相关。如果 dp[k][i] 存的是“恰好 k 次”最后一定要对 k 取 min。我见过有人最后直接输出 dp[K][N]结果在某个测试点 WA 了原因就是 K 次不是最优的少用一次反而更好。继承写法能一劳永逸避免这个问题。第三个坑其实最容易排查因为只要把中间变量输出出来基本一眼就能看到负数或者巨大的异常值。a[i] 是 10^6 级别区间长 400cost 最大值 4 亿再往上累加轻松超过 int。所以从一开始就统一用 long long 最省心。关于“初始展开”的歧义我想多说两句。不同 OJ 对题面的翻译存在差异有的把最开始那次展开算进 K 次有的不算。标准 USACO 语义下是算的这也是为什么样例在 K 1 时答案是 3 而不是 1。如果你在某个平台提交发现样例行为相反最简单的处理是读入 K 后把 K 加 1这样“最多 K 次调整”就包含了初始设置。我建议写代码之前先用手算样例确认语义避免在错误模型上调半天。最后一个技巧调试的时候可以自己构造 K N 的情况。因为每一组蛇都可以单独设一个刚好合适的网理论上浪费可以是 0。如果 K N 时程序输出不是 0说明转移过程有问题通常出在 j 的枚举范围或者 INF 处理上。这个检查非常快建议每次写完都顺手测一下。6. 实测表现与刷题心法这道题教会我的事我本地简单测了一下最坏情况N 400K 400所有 a[i] 随机生成。程序运行时间在 0.1 秒量级内存占用 3 MB 左右。对于信奥评测环境来说这个复杂度完全不需要优化。64M 次枚举对 C 来说是小场面关键是把状态定义想准别在边界上翻车。这道题给我最大的启发是很多看似操作类的题目只要找到“操作次数 分段数”这个对应关系就能直接转化成经典 DP。你不需要去模拟每一次调网只需要把网固定尺寸的那段时间看成一个段段的代价可以预处理剩下就是枚举切分点。类似的套路在“任务调度”“木棍切割”“分组求最大值”这些题目里反复出现本质都是把连续区间切成若干块然后用区间代价做转移。我个人练习时的习惯是拿到这种题先手算两个小样例一个是 K 很小的情况一个是 K N 的情况。K 很小能帮你理解为什么必须用大网覆盖长段K N 能帮你验证分段完全自由时答案是否合理。手算完再写代码边界条件会清晰很多。最后分享一个小技巧这种二维 DP 写完之后不需要急着交先打印一次 dp[K][N]再打印 min_{0tK} dp[t][N]如果两个值不一样说明你的“最多 K 次”语义没做对。这两个值本该相等因为继承逻辑已经保证了 dp[K][N] 是前缀最小值。用这个小检查能省掉不少无谓的 WA。
阅读完成 · 觉得有帮助？
