1. 别被题面带偏先把“颅脑损伤”抽象成DP最近在洛谷刷动态规划题单做到P8591 『JROI-8』颅脑损伤 2.0标的是普及一道典型的线性DP。说实话第一次看到“颅脑损伤”四个字还以为是什么医疗模拟题仔细读题才发现骨子里就是经典的“不相邻选择”问题给你一排数据每个位置有一个价值你可以在某些位置做操作但相邻两个位置不能同时操作问最多能拿到多少价值。这种模型放在医学背景下就变成了“脑区不能连续修复否则会产生二次损伤”本质完全没变。这道题对新手来说难点不在算法本身而在“从题面到状态设计”这一步。很多人一看到DP就慌觉得状态方程是天降的。实际上所有线性DP都有套路可循先明确阶段再确定每个阶段需要记录哪些关键信息最后把信息塞进状态里。P8591就是个特别好的练手题它把“相邻限制”这个最常见的DP约束包装得很有迷惑性拆穿了以后代码可能不到二十行。这篇复盘我会把当时从读题到AC的完整思路写下来包括状态是怎么一步步推出来的、转移方程为什么要长那样、边界条件有什么讲究、滚动数组怎么优化以及我自己踩过的坑。如果你刚学线性DP或者总觉得自己状态设计“全靠猜”这篇文章值得看完。1.1 从题目背景里提取核心模型题目给我们一个长度为n的数组aa[i]表示第i个脑区的损伤值。修复一个脑区就能得到a[i]的收益但是相邻两个脑区不能同时修复——原因题面里给了个很合理的设定连续修复会加重伤势得不偿失。目标是在这个限制下最大化收益总和。把这个医学背景剥掉剩下的是有n个物品排成一列每个物品有一个价值a[i]选择不能包含相邻的两个物品求选出来的物品价值之和的最大值。这就是“打家劫舍”的经典模型很多人一眼就能认出。但为什么洛谷标的是普及而不是普及-因为题目表面简单实际上对DP状态设计的理解有要求。如果只是背过“打家劫舍”的模板遇到稍微变一变的题目还是会栽。P8591恰恰就是在基础模型上做包装考验你能不能透过现象看到本质。1.2 为什么说这是一道“状态机”题“状态机”这个词听起来吓人其实就是指当前位置的决策受到前一个位置状态的影响。在这个问题里如果第i个脑区要修复那么第i-1个脑区必须不修复如果第i-1个脑区已经修复了那第i个脑区就只能跳过。换句话说每一步决策的“合法选项”是由上一步的选择决定的。这种“前一步影响后一步”的问题一维DP很难处理。因为一维dp[i]只记录“前i个的最大收益”它丢了“第i个到底选没选”这个信息。没有这个信息到了i1步就不知道能不能选。所以我们必须用二维数组把“当前最后一个位置的状态”也记下来。这就是这类题的核心思路加一个维度用来保存影响未来决策的信息。2. 状态设计从“一维不够用”到“二维刚刚好”2.1 一维dp[i]为什么必然出错很多初学者会写出这样的状态dp[i]表示前i个脑区能获得的最大收益。然后尝试转移dp[i] max(dp[i-1], dp[i-2] a[i])这个式子其实也能做对因为它隐含了一个结论如果不选第i个答案就是dp[i-1]如果选第i个那么第i-1个不能选所以最优是dp[i-2] a[i]。但问题是这个转移成立的前提是“前i-2个的最优解一定不会选第i-1个”而dp[i-2]本身没有这个保证。举个例子a [100, 1, 100] 用上面那个式子算 dp[1] max(dp[0], dp[-1]100) 100 dp[2] max(dp[1], dp[0]1) 100 dp[3] max(dp[2], dp[1]100) 200碰巧对了。但如果a [10, 100, 10] dp[1] 10 dp[2] max(10, 0100) 100 dp[3] max(100, 1010) 100答案是100但正确选法是选第1和第3个收益20不对101020比100小。正确答案是100。这里没出错。换个例子a [8, 9, 8] dp[1]8 dp[2]max(8,09)9 dp[3]max(9,88)16正确选第1和第3收益16。dp[3]的转移用了dp[1]a[3]但dp[1]是最优等于第1选或不选的最大值而它恰好选了第1个没问题。但实际上dp[i-2]可能对应“选了第i-2个”的方案也可能对应“没选第i-2个”的方案而这两种方案在转移时对未来的影响完全不同。看反例 a [5, 1, 5, 1] 用 dp[i] max(dp[i-1], dp[i-2] a[i]) dp[1]5 dp[2]max(5,01)5 dp[3]max(5,55)10 dp[4]max(10,51)10 正确选第1和第3收益10没错。再试一个 a [100, 1, 1, 100] dp[1]100 dp[2]max(100,01)100 dp[3]max(100,1001)100 dp[4]max(100,100100)200 正确选第1和第4收益200没问题。其实这个一维递推对“打家劫舍”这种不相邻模型是正确的原因是dp[i-2]本质上已经保证了第i-1个不选因为如果dp[i-2]选了第i-2个由于不相邻第i-1个自然不选如果dp[i-2]没选第i-2个那么dp[i-2]可能选了第i-3个但这对第i-1个没有限制仍可以选第i-1个等等这里有问题dp[i-2]如果没选第i-2个那它可能选了第i-3个使得第i-1个仍然可以选没有问题。所以dp[i-2] a[i]方案中第i-1个不选是必然的因为dp[i-2]最多考虑到i-2位置i-1位置没有被选。因此一维递推也是对的。但是一维dp虽然正确却很难扩展。如果你把题目改一点比如“不能连续选择超过2个”一维dp就完全无能为力了。P8591作为普及一般训练的是二维DP思维。所以我后面还是会用二维状态来讲解这是更通用、更符合“线性DP”教学价值的方式。2.2 二维状态的定义与转移我们规定dp[i][0]考虑前i个脑区并且第i个脑区不修复时能得到的最大收益dp[i][1]考虑前i个脑区并且第i个脑区修复时能得到的最大收益。因为“不能相邻修复”所以第i个脑区如果修复那么第i-1个脑区一定不能修复第i个脑区如果不修复那么第i-1个脑区修复或不修复都行取两者最大值。于是转移方程就是dp[i][0] max(dp[i-1][0], dp[i-1][1])dp[i][1] dp[i-1][0] a[i]这就是线性DP里最常见的“0/1两态转移”。你可以把dp[i][0]和dp[i][1]看成两个互相牵制的状态每走一步它们都会根据上一步的对方或自己来更新。这种写法最大的好处是状态转移完全透明每一步都明确知道当前位置选了没有不会出现一维DP那种“信息丢失”的隐患。2.3 一个带数值的推导示例假设a [3, 5, 2]初始状态dp[0][0] 0dp[0][1] -INF第0个位置不存在不能选。i1 dp[1][0] max(dp[0][0], dp[0][1]) max(0, -INF) 0 dp[1][1] dp[0][0] a[1] 0 3 3i2 dp[2][0] max(dp[1][0], dp[1][1]) max(0, 3) 3 dp[2][1] dp[1][0] a[2] 0 5 5i3 dp[3][0] max(dp[2][0], dp[2][1]) max(3, 5) 5 dp[3][1] dp[2][0] a[3] 3 2 5最终答案max(dp[3][0], dp[3][1]) 5。最优方案是只修复第2个脑区收益5或者修复第1和第3个脑区收益也是325。两种方案都符合“不相邻”限制。看到这里你可能会问dp[2][1] 5表示选了第2个那么dp[3][1]用dp[2][0]来转移也就是“第2个不修复”所以第3个可以修复得到325。这个流程非常清晰。如果把dp[i][0]和dp[i][1]放在一张表里每一步都能对应到实际方案这就是二维DP的好处。3. 代码实现从朴素二维到滚动数组3.1 完整C代码直接上我AC时的代码加了注释#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n 1); for (int i 1; i n; i) { cin a[i]; } // dp[i][0/1]初始化全部为0 vectorvectorint dp(n 1, vectorint(2, 0)); const int NEG_INF -1e9; dp[0][1] NEG_INF; // 第0个脑区不存在不能修复 for (int i 1; i n; i) { dp[i][0] max(dp[i - 1][0], dp[i - 1][1]); dp[i][1] dp[i - 1][0] a[i]; } cout max(dp[n][0], dp[n][1]) \n; return 0; }这里有个小细节dp[0][1] -1e9是为了逻辑上的完整性。实际上dp[i][1]只用到了dp[i-1][0]所以就算dp[0][1]设成0也不会影响结果但设成负无穷更符合语义第0个位置不存在你不能“修复”一个不存在的东西。以后如果题目扩展成“每个位置有三种状态”这种初始化的作用就体现出来了。3.2 边界条件为什么要这样处理边界最容易错的是dp[0][0]和dp[0][1]。dp[0][0]表示前0个脑区并且“第0个不修复”这种状态是合法的收益自然是0dp[0][1]表示前0个脑区但“第0个修复”这根本不可能所以设为负无穷这样当i1时如果错误地从dp[0][1]转移就会被负无穷拉低不会污染答案。有的同学喜欢从i1开始初始化dp[1][0] 0; dp[1][1] a[1];然后从i2循环也可以。但这样代码里需要多一个特判而且后续如果要改成滚动数组统一从0开始更简洁。我习惯把dp[0]当作“空序列”的基准状态这样循环从1到n代码结构整齐也不容易漏边界。3.3 空间优化滚动数组的写法与坑因为dp[i]只依赖dp[i-1]二维数组开n×2其实也不大但很多题目n会到10^5甚至10^6开二维数组虽然也能过2×10^6个int大约8MB但为了养成好习惯建议直接用滚动变量。简单做法是int dp0 0; // 相当于 dp[i-1][0] int dp1 -1e9; // 相当于 dp[i-1][1] for (int i 1; i n; i) { int new0 max(dp0, dp1); // 不选第i个 int new1 dp0 a[i]; // 选第i个则上一个必须不选 dp0 new0; dp1 new1; } cout max(dp0, dp1) \n;注意这里一定要用new0、new1暂存不能写成dp0 max(dp0, dp1); dp1 dp0 a[i]; // 错这里dp0已经是更新后的值了因为计算dp1时需要的是旧的dp0也就是第i-1个不选时的最大收益如果先更新dp0那么dp1里用到的就是“前i个不选的最大收益”转移就错了。这个坑我至少见过三次滚动数组版本尤其容易犯。你可以在纸上把新旧值分别标记就不会搞混。更稳妥的写法是同时用一个临时变量保存旧dp0int old0 dp0; dp0 max(dp0, dp1); dp1 old0 a[i];这种写法更贴近“先把旧值保存下来再用”的思路也不容易出错。4. 实战中踩过的坑与排查技巧4.1 状态初始化最容易忽略的“隐藏负值”如果题目中a[i]可能是负数有些同学会在初始化时把所有dp都设成0然后发现答案一直是0。这其实是混淆了“收益可以为负”和“我们可以选择不修复任何脑区”这两件事。在这个模型里每个脑区可以跳过所以最终答案一定不会小于0。但这不代表dp[i][1]不能为负。dp[i][1]表示“第i个必须修复”时的最大收益如果a[i]是负数那么dp[i][1]完全可能是负数。我们在算最终答案时取max(dp[n][0], dp[n][1])dp[n][0]至少是0所以答案不会被负数污染。但如果你的初始化把所有dp都设成0那dp[i][1]就可能不正确地大于真实值比如从0加上负数结果变成负数这没问题但如果你把负无穷写成-1e9然后max比较没问题。真正需要注意的是如果a[i]的范围特别大-1e9可能不够小要用-0x3f3f3f3f或者-4e18long long。我用int时习惯设-1e9因为一般a[i]绝对值不超过1e5但如果题目没给范围还是用long long和-4e18比较稳妥。4.2 转移顺序滚动数组版专属坑前面提到过滚动数组里先更新dp0再更新dp1是错的。这种错误在二维数组版本不会出现因为dp[i][1]用的是dp[i-1][0]下标不同天然隔离。但滚动数组只有两个变量顺序就变得关键。我建议如果你对滚动数组不熟先在纸上写下“旧dp0 上一次的dp0旧dp1 上一次的dp1”然后对照转移方程一步步来。还有一个类似的问题如果先用dp1更新dp0再用dp0更新dp1也会出错。正确做法是同时基于旧值计算新值再用新值覆盖旧值。这也是为什么我推荐先用临时变量保存旧值的写法。4.3 数组大小和越界如果n最大是10^6二维vector (n1, vector (2,0)) 大约8MB没问题。但如果n到10^7内存可能紧张。这时候滚动数组几乎是必须的。另外要注意下标从1开始给a开n1空间。读入时不要越界循环从1到n。很多同学习惯从0开始读然后状态转移时下标对不上很容易错位。P8591这种线性DP题下标从1开始会让代码直观很多推荐。4.4 肉眼Debug小技巧把dp表打出来遇到样例过不了的时候我最常用的方法就是在循环里加一行输出把每个i的dp[i][0]和dp[i][1]都打出来然后对着自己手算的递推过程检查。比如你怀疑第二步转移错了直接看dp[2][0]和dp[2][1]是否符合预期。具体可以这样for (int i 1; i n; i) { dp[i][0] max(dp[i-1][0], dp[i-1][1]); dp[i][1] dp[i-1][0] a[i]; cerr i i dp0 dp[i][0] dp1 dp[i][1] \n; }然后拿一组极小的数据比如n3a[1,2,3]手动算一遍对比输出。这个方法比瞎猜效率高得多。后来我写多了甚至会在blcok注释里把dp的定义写上去防止写着写着忘记状态含义。4.5 一个小众但致命的坑读入优化洛谷这类题输入量一般不大cin加sync_with_stdio(false)足够。但如果n很大推荐scanf或者用快读。很多人以为IO不是问题结果TLE在输入上。虽然这题更偏向考DP但养成好习惯总没错。另外用C写的时候注意把a[i]读进来时用int还是long long一并想好别后面改起来麻烦。5. 从P8591到更多动态规划题怎么做到举一反三5.1 抽象出“状态机”思维模板P8591的核心不是“不相邻选择”本身而是背后的状态机思考方式当后一步的合法决策取决于前一步的某个状态时就把那个状态加进DP数组的维度。这个套路适用范围很广常见的有不能相邻选择0/1两态不能连续选择超过k个状态加一维“当前位置连续选了多少个”股票买卖状态加一维“持有/不持有”括号匹配状态加一维“当前未匹配的左括号数”。一旦你习惯了“加一维记录状态”很多看似很新的DP题其实都是老朋友换了个马甲。5.2 变体一不能连续选择超过2个如果题目改成“不能连续修复相邻的两个脑区”和现在一样我们用的是0/1。但如果改成“不能连续修复超过2个脑区”也就是最多可以连续选2个不能连续选3个那么DP状态需要记录“当前已经连续修复了0个、1个还是2个”。可以定义dp[i][0]表示第i个不修复前i个的最大收益dp[i][1]表示第i个修复且第i-1个不修复也就是以当前位置结尾连续长度为1dp[i][2]表示第i个修复且第i-1个也修复连续长度为2。转移是dp[i][0] max(dp[i-1][0], dp[i-1][1], dp[i-1][2]) dp[i][1] max(dp[i-1][0]) a[i] dp[i][2] dp[i-1][1] a[i]这就是把状态从2个扩展成3个。你看核心逻辑没变只是状态多了。这也是为什么我强调一开始就用二维写法因为扩展起来特别自然。5.3 变体二线性改成环形如果题目再变一下说脑区是一个环第一个和最后一个也算相邻那处理方式就是“破环成链”分别讨论第1个选/不选两种情况做两次线性DP取最优。因为环形问题的麻烦在于首尾互相影响而线性DP只能处理单向影响所以枚举一下首位置的状态就可以变成两个独立线性问题。这部分虽然P8591没考但它是“打家劫舍”系列里最常见的扩展。动态规划题单里这类题目非常多把线性版本吃透再去看环形版本会有一种“原来如此”的通透感。5.4 刷题建议不要急着看题解很多人在洛谷刷题时看到普及就直接去搜题解结果下次遇到还是不会。我的经验是拿到一道DP题先花二十分钟自己设计状态。设计错了也没关系错的过程也会让你理解“为什么要多一维”。比如这道题你可以先试试一维dp能不能做然后发现信息不够最后自然推演出二维。这个过程比直接背二维状态要宝贵得多。刷题时也可以把同类题放在一起做。比如“打家劫舍”系列、股票买卖系列、背包问题系列它们的状态设计都有相似之处。P8591这种题本身代码量很小但背后的模型可以衍生出很多变体。我建议你专门用一个笔记记下“状态设计清单”目标是什么阶段的划分是什么每一步有哪些合法决策上一个状态怎么影响当前决策把这些问题回答清楚转移方程就水到渠成了。我个人做完P8591之后把“不能相邻选择”的0/1状态模型整理成了一个模板然后去做了好几道类似题包括环形打家劫舍、需要滚动数组的高数据范围版本效果很好。动态规划就是这样第一次见觉得难见多了就会发现套路就那么几个。而P8591这道“颅脑损伤 2.0”就是帮你把“加一维记录状态”这个套路刻进DNA的一道好题。最后分享一个我自己的小习惯代码注释里不只写“dp[i][0]表示第i个不选”还要写明“为什么要分0和1”一句话。比如写“0/1分别记录上一个位置选没选用于处理相邻限制”。这样一个月后再翻代码一眼就能看懂不用重新推理一遍。这个习惯在算法竞赛里很管用毕竟做过题的人都知道最痛苦的不是当时写不出而是三个月后看自己的代码像看天书。