看到P8591这个编号再加上那个让人血压上升的标题《『JROI-8』颅脑损伤 2.0》我当时的第一反应就是这大概又是一道要把人绕成麻花的普及动态规划题。打开洛谷的动态规划题单你会发现“线性DP”这一档永远不缺少这种名字很皮、实际更皮的题目而P8591恰恰就是典型代表。今天这篇文章我不打算做一个“贴标答”的简单题解我更想完整讲清楚拿到一道不认识的DP题应该怎么把题面刨开、怎么定义状态、怎么把转移方程写稳、怎么用对拍验证自己没写错以及面对“2.0”这种加强版时到底该警惕哪些坑。这道题出自 JROI-8 的比赛序列难度定位在普及正好卡在一个尴尬的位置你说它难吧它没有让你做斜率优化、矩阵快速幂这类高级操作你说它简单吧如果你只会套模板又很容易在“状态到底开几维”这个地方翻车。我自己的做题经验是这种题目最考验的不是算法知识量而是建模能力。换句话说你能不能把一个看起来花里胡哨的故事翻译成一个干巴巴的数组递推。能过了这一关代码是你自己的思路才是真正值钱的。1. 拆题与建模把“手术故事”翻译成“序列决策”1.1 题面里的操作是建模的唯一线索我做竞赛题有个习惯读题先不关心故事背景只看“数据形态”和“操作约束”。像“颅脑损伤”这种题名大概率会给你一个长度为 n 的序列然后告诉你某些位置会被标记、会被治疗、会被切除、会被替换——反正就是给你一个一维数组再加一些规则让你求某个最小值或最大值。你可能会问为什么一定是从左到右扫一遍的线性DP而不是区间DP、树形DP、状态压缩DP其实判断起来很简单如果整个计算过程只需要维护“当前扫到哪个位置”以及“这个位置周边的少数几个状态”那就是线性DP的范畴如果答案依赖任意一个区间内部的划分那就更接近区间DP。P8591这一类“普及”题目绝大多数都是前者。你真正需要做的是从题面里找出三件事决策的单位是什么通常就是“每个位置选或不选”“每个位置取哪种操作”。操作之间有怎样的限制比如相邻两个位置不能同时选或者连续多少个位置必须至少选一个。代价怎么计算选一个位置要付出多少不选又要付出多少。这三件事一旦清晰DP的骨架基本上就立起来了。很多选手喜欢一上来就猜状态结果被故事的“手术”“仪器”“缝合”这些词带跑偏。我的建议是把故事彻底忽略直接在草稿纸上写 n 和操作规则这样反而最快。1.2 线性DP的通用骨架从左往右扫线性DP的核心思想用一句话说就是每次只处理前缀前 i 个位置的结果可以从前 i-1 个位置的结果递推过来。你不需要回头去看整段历史只需要保留“影响未来决策”的那点信息。这就像排队做核酸你不需要记住队伍里每个人的所有细节只需要知道当前轮到谁、他前面那个人有没有检测过、当前队伍满不满员。放在DP里就是“当前下标”加“有限个关键状态”的二维数组甚至某些情况下一维数组也够用。P8591如果只有一个限制条件那状态很可能就是 f[i][0/1] 这种二态写法如果像“2.0”加强版一样同时存在两个以上限制那就可能得开三态甚至四态。不过别怕状态多不代表思路杂你只需要按顺序处理每种状态对应的转移即可。1.3 状态里到底该装什么我知道很多新手最纠结的就是这个问题我到底该用 f[i][0] 还是 f[i][1]还是干脆 f[i][j][k]这里有一条非常朴素但有效的判断标准状态里必须包含“当前这一步结束之后对后续决策有影响的全部信息”。举例来说如果规则是“不能连续选择相邻的两个位置”那么当你准备决策第 i 个位置时唯一需要知道的就是第 i-1 个位置有没有被选择。所以你用一个 f[i][0/1] 就足够了0 表示第 i 个位置不选1 表示第 i 个位置选。如果规则变成“连续不选的位置不能超过两个”那你可能就得知道最后连续有几个位置没选这时状态需要扩展成 f[i][k]k 表示末尾连续不选的数量。再如果规则变成“选择某个位置会影响未来两个位置的代价”那你可能还需要记录 i-1 和 i-2 两个位置的状态。这就是为什么状态数组的维数不是拍脑袋定的而是由“记忆需求”决定的。2. 状态设计与转移方程从暴力思想到递推公式2.1 先想暴力再压缩状态我做这类题时有一个习惯先想一个最暴力、最没脑子的枚举方案。比如如果每个位置有三种操作方式那 n 个位置总共有 3^n 种方案肯定不可行。但暴力方案的好处是能帮你明确“最终答案需要覆盖哪些情况”。然后再做减法从 3^n 变成 3n靠的是“无后效性”和“阶段性”。只要当前决策只依赖前一个位置的少量信息你就可以扔掉更早的历史。这就像你只需要知道上一个路口往哪转了不需要把三年前的路况都翻出来。对 P8591 这种普及题目最终状态几乎可以确定是二维数组下标 i处理到第几个位置第二维当前位置选择的状态类别至于是两类还是三类取决于题面到底要求“每个位置必有且仅有一种操作”还是“某些位置可以不操作”。我在这里先给出最常见的二态结构后面会在3.3节给出完整代码骨架。如果你做题时发现原题有三类状态你只需要把二态逻辑复制扩展成三态即可思考方式完全一致。2.2 转移方程背后的“最后一步”思维转移方程为什么总是一大堆 min、max 套在一起本质原因是你没法确定最优方案到底选择了哪条路所以你只能把所有可能的前一个状态都算一遍然后取最优值。拿一个非常经典的“相邻不可同时选”模型来说假设 w[i] 是选择第 i 个位置的代价如果第 i 个位置不选那它和前一个位置选不选都没关系如果第 i 个位置选那前一个位置必须不选。于是f[i][0] min(f[i-1][0], f[i-1][1]) // 当前不选前一个随意 f[i][1] f[i-1][0] w[i] // 当前选前一个只能不选这个转移的含义其实只有一句话“你在第 i 个位置能做哪些选择完全取决于第 i-1 个位置留下的合法状态。”你在草稿纸上推转移时不要急着写代码先用笔把这句“取决于”写出来。写清楚之后方程自然就出来了。如果原题模型是“覆盖型”——比如要求任意相邻两个位置至少有一个被选——那么转移会是f[i][0] f[i-1][1] // 当前不选前一个必须选 f[i][1] min(f[i-1][0], f[i-1][1]) w[i]你看两种模型只差一个地方但代码完全不同。所以这也是为什么我不建议直接背模板而是每次做题都老老实实先理清约束。2.3 用手算小样例验证转移方程推完之后我强烈建议你拿一个长度为 3 或 4 的小数据手动算一遍。比如 n3w [2, 5, 3]按上面第二个模型算一下f[1][0] INF因为第一个位置不选前面没有位置不合法f[1][1] 2f[2][0] f[1][1] 2f[2][1] min(f[1][0], f[1][1]) 5 2 5 7f[3][0] f[2][1] 7f[3][1] min(f[2][0], f[2][1]) 3 min(2, 7) 3 5最终答案取 min(f[3][0], f[3][1]) 5。你手算完之后再用代码跑一遍如果答案一致基本可以确认转移没有原理性错误。这一步看起来很笨但它能节约你大量的调试时间。3. 初始化、边界与实现细节3.1 初始化是WA的万恶之源很多人的DP代码明明转移写对了却还是WA问题十有八九出在初始化。你要想清楚一个物理意义下标 0 代表“一个位置都没处理”那么 f[0][0] 是合法的表示“前0个位置且最后一个位置处于未选择状态”的代价是 0但 f[0][1] 通常是不合法的因为没有任何位置可供选择。所以初始化应该写f[0][0] 0; f[0][1] INF;这个 INF 要设置多大如果代价总和可能达到 1e14你设置 INF 1e9 就会溢出或出错。竞赛里我一般直接写成long long INF 1e18;并且所有 f 数组都用 long long防止两个有效值相加后爆了 int 的 2e9 上限。你可能觉得这是常识但我见过太多次因为 int 溢出导致答案莫名变负数的惨案。3.2 边界条件不是“不越界”就完事了边界条件的本质是要你回答一个问题最终答案应该从哪个状态里取如果问题是求“处理完所有位置之后的最小代价”那答案通常需要取 min(f[n][0], f[n][1])。但有些题会要求“最后一个位置必须满足某种状态”那你取答案时就必须夹紧这个条件。还有一种很容易出错的边界是当 n 很小比如 n1 或 n2 时你的转移是否还能成立如果 n1f[1][0] 和 f[1][1] 都必须能由初始化合法推出。很多选手在 n1 时才发现自己的 f[1][0] 被推导成了一个荒谬的 INF。解决方法是在写完代码后专门用 n1、n2、n3 三组数据去跑。这三组数据如果没问题边界基本就稳了。3.3 一个可以直接上手改的代码骨架下面是我做“扫描线性DP”时常用的 C 骨架你拿到原题之后只需要把状态数量、转移分支、代价函数三个地方替换掉就能快速得到一版可运行的代码。#include bits/stdc.h using namespace std; const long long INF 1e18; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorlong long w(n 1); for (int i 1; i n; i) { cin w[i]; } // f[i][0]处理完前i个位置且第i个位置未被选择 // f[i][1]处理完前i个位置且第i个位置已被选择 vectorvectorlong long f(n 1, vectorlong long(2, INF)); f[0][0] 0; for (int i 1; i n; i) { // 当前不选前一个必须选覆盖型约束示例 f[i][0] f[i - 1][1]; // 当前选前一个可选可不选 f[i][1] min(f[i - 1][0], f[i - 1][1]) w[i]; } cout min(f[n][0], f[n][1]) \n; return 0; }这个骨架里我用的覆盖型约束只是示例。你真正写P8591时一定要根据题面里的“连续限制”“禁止相邻”等具体规则调整分支。记住了骨架只是起点翻译题面才是核心。4. 现场踩坑清单常见问题与排查实录4.1 我犯过的几个低级错误先交代一下我在这类普及DP题上栽过不少次跟头下面这些坑基本都是真实发生过的第一个是把 INF 开小了。某次我开了 0x3f3f3f3f也就是大概 1e9然后题目代价累加能达到 1e10结果 INF 加上一个正数反而小于某些真实的代价转移方程直接选出错误状态。这属于“报错不报错都看不出来的玄学bug”。第二个是忘记处理“非法状态”。举个例子f[i][0] 在某些模型里要求第 i-1 个位置必须选但如果你把第 1 个位置的 f[1][0] 从 f[0][1] 推过来而 f[0][1] 恰好是 0那就等于凭空让了一个合法状态答案直接被污染。初始化时一定要仔细凡是从物理意义上说不通的状态全部设为 INF。第三个是滚动数组优化时把状态写串了。线性DP的 f[i] 只依赖 f[i-1]所以理论上可以只留两个一维数组。但“理论可以”不等于“顺手压缩”如果你边写边压很容易把 f[i][0] 写成 f[i-1][1] 和 f[i-1][0] 混在一起等发现时已经很难查了。我现在的习惯是先用二维数组写对测试通过后再考虑滚动而不是一上来就滚动。4.2 常见问题速查表为了方便你对照我把经常会遇到的问题整理成了一个小表格。如果提交后出现对应症状直接按右边的思路去查。症状可能原因排查方向答案比预期小很多INF 设置过小非法状态被当成合法状态参与转移检查初始化增大 INF检查 f[0] 的所有状态答案比预期大很多转移分支漏了一种合法情况或约束条件写严了回到“最后一步”推导看当前状态能由哪些前驱到达小数据对拍没问题大数据WA使用了 int 导致溢出全局换成 long longn1 或 n2 时影死循环或越界循环边界或状态下标写错单独测试 n1、n2下标一律从 1 开始答案输出为负数组越界改到了相邻内存位检查容器大小排查 i-1 或 i-2 的越界可能这个表不是万能的但覆盖了我见过的大部分低级错误。如果你按表排查完还是不对就别盯着代码死磕了老老实实写个暴力对拍这才是最高效的定位方法。5. 怎么验证DP正确性暴力对拍才是王道5.1 为什么要写暴力你可能会想我DP都写完了为什么还要写一个指数级复杂度的暴力程序因为暴力的正确性显而易见它枚举所有方案取最优值几乎不可能写错。而DP的转移是靠逻辑推导出来的一旦推导中有盲区你盯着代码看两个小时都看不出来。对拍的意义就是用明显正确的暴力去验证逻辑复杂的DP。只要在大量随机数据上两者结果完全一致你才能放心地说“这道题我是真会了。”5.2 对拍脚本怎么写对拍通常需要三个文件数据生成器、暴力程序、DP程序。数据生成器最好用随机数范围不要太大让暴力能跑得动。比如 n 取 1 到 10w[i] 取 1 到 20这样暴力枚举 2^n 或者 3^n 是完全来得及的。暴力程序写起来相当直接比如枚举每个位置选或不选再检查是否满足约束求最小代价。下面是一个简单的伪代码思路ans INF for mask in 0 .. (1 n) - 1: ok true for i in 1 .. n: if 约束不满足: ok false if ok: cost 计算mask对应的总代价 ans min(ans, cost) print(ans)然后写一个 shell 脚本循环跑for i in $(seq 1 1000) do python3 gen.py input.txt python3 brute.py input.txt ans_brute.txt ./dp_solution input.txt ans_dp.txt if ! diff -q ans_brute.txt ans_dp.txt /dev/null; then echo WA on test $i break fi done echo done我一般用 Python 写数据生成器和暴力因为快不用编译。C 的程序就编译好之后再调用。脚本逻辑很简单核心就是“不停地生成随机数据并比对结果”。只要中途出现一次 diff就意味着找到了一个反例这时候把 input.txt 留着用来人工分析。5.3 对拍找到反例后怎么修一旦发现DP和暴力结果不一致第一步不是拍脑袋改转移而是人工跑一遍那组小数据找出最优方案到底是什么。然后对着你的DP状态一步一步算看它在哪里丢掉了最优方案。绝大多数情况下你会发现问题出在“某个状态不能被某个前驱状态转移过去”也就是状态转移漏掉了一个分支。这时回到2.2节重新用“最后一步”思维推导一遍通常很快就能找到。对拍还有一个额外好处它能帮你建立信心。在真实比赛里你没有时间反复怀疑自己的DP对不对但如果平时养成了“写完就拍”的习惯比赛时你会更果断地提交不再纠结那几毫秒。6. 从这道题向外走DP骨架能迁移到哪6.1 “车辆动态规划问题”和竞赛DP有什么关系搜索这道题时你会看到一些关联热词比如“车辆动态规划问题”“洛谷动态规划题单”看起来和脑外科手术八竿子打不着。但你要是把“车辆”替换成“位置”“城市”“站点”就会发现它仍然是同一个骨架在一维或多维空间上顺序决策每个位置保留若干个状态通过局部转移求全局最优。做车辆调度时要考虑车辆的剩余容量、当前位置、时间窗本质上就是在状态里存住这些“影响未来”的信息。很多人的误区是背了无数模板却不明白状态设计的思想。所以我要反复强调的是你不需要背P8591的转移你需要背的是“最后一步思考法”和“状态取舍原则”。前者解决方程怎么推后者解决数组怎么开。这两个习惯比任何模板都值钱。6.2 向更高难度的DP题升级会怎么改P8591难在普及“2.0”这个后缀暗示它已经比原版多加了一些限制但核心还是没有离开线性DP。如果以后再遇到难度更高的线性DP你会发现往往只是这三件事变了第一状态数量变多可能是五六个分类第二转移需要用前缀最小值或单调队列优化第三数据范围变大需要滚动数组压内存。但只要你在这个题里练好了“拆题、设状态、推转移、写对拍”这一整套流程后续升级你接得住不会慌。我从个人经验来说竞赛里很多所谓“难题”并不是一步登天的新算法而是把基础DP加上一些限制条件逼你多想一层。你在这个题上多花的每一分钟都是在给后面的难题铺路。所以如果你真的把这篇文章从头看到这里我建议你关掉文字老老实实打开题目列表按本文的步骤亲手写一遍再写个暴力对拍直到所有随机数据都能过为止。这个“亲手走完流程”的过程才是你真正的收获。