看到P8591这个编号，再加上那个让人血压上升的标题《『JROI-8』颅脑损伤 2.0》，我当时的第一反应就是：这大概又是一道要把人绕成麻花的普及+动态规划题。打开洛谷的动态规划题单，你会发现“线性DP”这一档永远不缺少这种名字很皮、实际更皮的题目，而P8591恰恰就是典型代表。今天这篇文章，我不打算做一个“贴标答”的简单题解，我更想完整讲清楚：拿到一道不认识的DP题，应该怎么把题面刨开、怎么定义状态、怎么把转移方程写稳、怎么用对拍验证自己没写错，以及面对“2.0”这种加强版时到底该警惕哪些坑。

这道题出自 JROI-8 的比赛序列，难度定位在普及+，正好卡在一个尴尬的位置：你说它难吧，它没有让你做斜率优化、矩阵快速幂这类高级操作；你说它简单吧，如果你只会套模板，又很容易在“状态到底开几维”这个地方翻车。我自己的做题经验是，这种题目最考验的不是算法知识量，而是建模能力。换句话说，你能不能把一个看起来花里胡哨的故事，翻译成一个干巴巴的数组递推。能过了这一关，代码是你自己的，思路才是真正值钱的。

1. 拆题与建模：把“手术故事”翻译成“序列决策”

1.1 题面里的操作，是建模的唯一线索

我做竞赛题有个习惯，读题先不关心故事背景，只看“数据形态”和“操作约束”。像“颅脑损伤”这种题名，大概率会给你一个长度为 n 的序列，然后告诉你某些位置会被标记、会被治疗、会被切除、会被替换——反正就是给你一个一维数组，再加一些规则，让你求某个最小值或最大值。

你可能会问：为什么一定是从左到右扫一遍的线性DP，而不是区间DP、树形DP、状态压缩DP？其实判断起来很简单：如果整个计算过程只需要维护“当前扫到哪个位置”以及“这个位置周边的少数几个状态”，那就是线性DP的范畴；如果答案依赖任意一个区间内部的划分，那就更接近区间DP。P8591这一类“普及+”题目，绝大多数都是前者。你真正需要做的，是从题面里找出三件事：

1. 决策的单位是什么？通常就是“每个位置选或不选”“每个位置取哪种操作”。
2. 操作之间有怎样的限制？比如相邻两个位置不能同时选，或者连续多少个位置必须至少选一个。
3. 代价怎么计算？选一个位置要付出多少，不选又要付出多少。

这三件事一旦清晰，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 的小数据手动算一遍。比如 n=3，w = [2, 5, 3]，按上面第二个模型算一下：

• f[1][0] = INF（因为第一个位置不选，前面没有位置，不合法）
• f[1][1] = 2
• f[2][0] = f[1][1] = 2
• f[2][1] = min(f[1][0], f[1][1]) + 5 = 2 + 5 = 7
• f[3][0] = f[2][1] = 7
• f[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 很小，比如 n=1 或 n=2 时，你的转移是否还能成立？如果 n=1，f[1][0] 和 f[1][1] 都必须能由初始化合法推出。很多选手在 n=1 时才发现自己的 f[1][0] 被推导成了一个荒谬的 INF。解决方法是，在写完代码后，专门用 n=1、n=2、n=3 三组数据去跑。这三组数据如果没问题，边界基本就稳了。

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; vector<long long> w(n + 1); for (int i = 1; i <= n; i++) { cin >> w[i]; } // f[i][0]：处理完前i个位置，且第i个位置未被选择 // f[i][1]：处理完前i个位置，且第i个位置已被选择 vector<vector<long long>> f(n + 1, vector<long 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 常见问题速查表

为了方便你对照，我把经常会遇到的问题整理成了一个小表格。如果提交后出现对应症状，直接按右边的思路去查。

这个表不是万能的，但覆盖了我见过的大部分低级错误。如果你按表排查完还是不对，就别盯着代码死磕了，老老实实写个暴力对拍，这才是最高效的定位方法。

5. 怎么验证DP正确性：暴力对拍才是王道

5.1 为什么要写暴力

你可能会想：我DP都写完了，为什么还要写一个指数级复杂度的暴力程序？因为暴力的正确性显而易见，它枚举所有方案，取最优值，几乎不可能写错。而DP的转移是靠逻辑推导出来的，一旦推导中有盲区，你盯着代码看两个小时都看不出来。对拍的意义就是：用明显正确的暴力，去验证逻辑复杂的DP。只要在大量随机数据上两者结果完全一致，你才能放心地说：“这道题我是真会了。”

5.2 对拍脚本怎么写

对拍通常需要三个文件：数据生成器、暴力程序、DP程序。数据生成器最好用随机数，范围不要太大，让暴力能跑得动。比如 n 取 1 到 10，w[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加上一些限制条件，逼你多想一层。你在这个题上多花的每一分钟，都是在给后面的难题铺路。所以如果你真的把这篇文章从头看到这里，我建议你关掉文字，老老实实打开题目列表，按本文的步骤亲手写一遍，再写个暴力对拍，直到所有随机数据都能过为止。这个“亲手走完流程”的过程，才是你真正的收获。