CSP-S 区间 DP 复习手册精简版·无代码覆盖 4 章 12 题保留状态定义、转移推导、复杂度、易错点删除全部程序代码。使用方式先看状态为什么这么定再看“最后一步”怎么拆最后记边界与易错点。目录第一章 区间 DP 入门与线性合并P1063 能量项链P3146 248第二章 区间消除与括号序列匹配3. P7914 超级括号序列4. CF1132F Clear the String5. P4290 玩具取名6. CF1312E Array Shrinking第三章 区间最值与构造7. CF1509C The Sports Festival8. ABC217F Make Pair9. CF1025D Recovering BST10. TTPC2024 E ReTravel11. ABC163E Active Infants第四章 区间 DP 优化进阶12. P4767 邮局附录P2679 子串为什么不是区间 DP方法速查表刷题顺序第一章 区间 DP 入门与线性合并区间 DP 的状态是「一段连续区间」[l,r]答案由更短区间合并而来。计算顺序外层枚举区间长度从小到大内层枚举左端点。本章核心线性合并 破环为链。1. P1063 [NOIP2006] 能量项链考点环形区间、线性合并、枚举分割点、long long。状态定义dp[l][r]把链上第l颗到第r颗珠子合并成一颗珠子时所能释放的最大能量。为什么这样定义每次操作都是相邻两颗合并成一颗最终把一整段合并成一颗。最后一次合并一定在某个位置把区间分成左右两段所以区间答案只取决于这段区间。破环为链项链是环。把序列复制一遍接在后面得到长度2n的链a[in]a[i]。任意一段长度为n的连续子链都对应环上一种断开方式。下标约定珠子i头标记为a[i]尾标记为a[i1]。区间[l,r]合并后头为a[l]尾为a[r1]。转移推导最后一步左段[l,k]合并成头a[l]、尾a[k1]的珠子右段[k1,r]合并成头a[k1]、尾a[r1]的珠子。两颗再合并释放a[l] * a[k1] * a[r1]。所以dp[l][r] max(dp[l][k] dp[k1][r] a[l] * a[k1] * a[r1])其中l ≤ k r。边界dp[i][i] 0。答案max dp[i][in-1]1 ≤ i ≤ n。复杂度时间O(n^3)空间O(n^2)。易错点最后乘的是a[l] * a[k1] * a[r1]不是a[l] * a[k] * a[r]。长度只枚举到n但端点范围要到2n。三个数相乘可能超过int用long long。2. P3146 [USACO16OPEN] 248考点区间 DP 记录数值、相等才合并、全程取 max。状态定义dp[l][r]若区间[l,r]能经过若干次合并变成一个数则记录这个数的值若不能则为0。题中数均为正所以0可作“不可行”标记。初始dp[i][i] a[i]。转移推导[l,r]要变成一个数最后一步必然是相邻两个数合并。即存在分割点k使[l,k]已合并成一个数、[k1,r]也已合并成一个数且两数相等若存在kl ≤ k r使dp[l][k] dp[k1][r]且非0则dp[l][r] dp[l][k] 1。同一区间若有多个可行k合并出的值相同直接赋值即可。答案计算过程中出现过的所有dp值的最大值含单元素。不是dp[1][n]因为整段未必能合成一个数。复杂度时间O(n^3)空间O(n^2)。易错点必须判断两边值非0且相等否则两个“不可行”的0会被误合并成1。答案是全程最大值不是整段值。第一章小结状态对准连续区间找最后一步枚举分割点按区间长度从小到大算。环形先破环为链。第二章 区间消除与括号序列匹配本章处理「消除」与「匹配」。难点不在状态本身而在转移结构完整、且不重复计数。P7914 是提高组计数去重代表务必吃透。3. P7914 [CSP-S2021] 超级括号序列考点文法解析、区间计数、多类转移不重不漏、前缀和优化。难度hard提高/省选−。题面关键字符(、)、*、?。?可替换成前三者任意一个。S表示 1~k 个*组成的非空串。规范序列规则()、(S)是规范序列若A、B规范则AB、ASB规范若A规范则(A)、(SA)、(AS)规范。求把所有?确定后得到规范超级括号序列的方案数模1e97。状态定义任何规范序列最左端一定是(最右端一定是)。规范序列分两个层次块最外层是一对互相匹配的括号形如(X)。序列由若干个块并列组成相邻块之间可夹 1~k 个*。定义bl[l][r]区间[l,r]恰好是一个「块」(X)的方案数。dp[l][r]区间[l,r]是规范「序列」的方案数。为什么要分层并列拼接时必须以“块”为最小单位枚举。直接在dp上随意切分同一方案会因切分点不同被重复统计。块bl[l][r]的转移两端必须能作括号s[l] ∈ {(, ?}s[r] ∈ {), ?}否则bl 0。剥掉最外层括号内部[l1,r-1]有四类互不相交情况内部为空()长度 2 时bl[l][r] 1。(S)内部全是*且长度 1~k贡献1。(A)内部整体是规范序列贡献dp[l1][r-1]。(SA)内部 1~k 个*后接规范序列贡献Σ dp[l1c][r-1]。(AS)内部 规范序列后接 1~k 个*贡献Σ dp[l1][p-1]。这四类不重不漏因为文法中没有(*A*)这种左右同时加星的形式。序列dp[l][r]的转移不能用dp任意拆两段否则会重复计数。例如三个块并列A B C会在A|BC和AB|C两处各数一次。正确做法固定枚举“第一个块”。设第一个块是[l,m]用bl[l][m]计数。其后两种延续直接相接bl[l][m] * dp[m1][r]中间隔 1~g 个*bl[l][m] * Σ dp[x][r]其中x从m2到m1gg min(k, nxtStar[m1])。再加上整个区间只有一个块bl[l][r]。所以dp[l][r] bl[l][r] Σ bl[l][m] * dp[m1][r] Σ bl[l][m] * Σ dp[x][r]。“第一个块”唯一所以每个方案恰好统计一次。前缀和优化固定(l,r)时第三项要的是dp[x][r]在一段连续x区间上的和。引入前缀和pref[u] Σ dp[x][r]x从l1到u。则区间和O(1)求出。连续可作*的长度用nxtStar[i]预处理O(1)判定。复杂度时间O(n^3)空间O(n^2)。易错点漏掉“单个块”dp[l][r]初值必须是bl[l][r]。并列重复计数必须按“第一个块[l,m]”枚举。隔*分支剩余起点从m2开始不是m1。(AS)枚举方向星串固定以r-1结尾星数超过k才 break。4. CF1132F Clear the String考点区间消除、相同字符端点共享一次操作。状态定义dp[l][r]把s[l..r]全部删除的最少操作次数。边界dp[i][i] 1。转移推导若s[l] s[r]删除其中一端的那次操作可以顺带把另一端一起删掉dp[l][r] min(dp[l1][r], dp[l][r-1])。一般枚举分割点dp[l][r] min(dp[l][k] dp[k1][r])。特别地若s[l] s[k1]可先删空中间(l1,k)再让s[l]与s[k1]在同一次操作中删除dp[l][r] min(dp[l][r], dp[l1][k] dp[k1][r])。复杂度时间O(n^3)空间O(n^2)。易错点不要漏掉普通拆分顺带删除只在字符相同时成立是额外优化不能替代普通拆分。5. P4290 [HAOI2008] 玩具取名考点区间可达性、变形规则、四字母状态。状态定义dp[l][r][c]子串[l,r]能否替换成字母cc ∈ {W,I,N,G}。单字符时只有它本身可行。转移推导若目标字母c可用一对字母(u,v)替代则枚举分割点k当dp[l][k][u]和dp[k1][r][v]都为真时dp[l][r][c] true。答案按W,I,N,G顺序输出dp[1][n][c]为真的字母若都没有输出错误信息。复杂度时间约O(n^3 * 规则数)空间O(n^2 * 4)。易错点这是可达性 DP不是计数也不是求代价。一个区间可能同时收缩成多个字母四个字母状态要分别维护。6. CF1312E Array Shrinking考点区间 DP 判定 线性 DP 组合求最短长度。第一步区间判定best[l][r]区间[l,r]能缩成一个数时的值否则-1。转移同 P3146若存在kbest[l][k] ! -1且best[l][k] best[k1][r]则best[l][r] best[l][k] 1。第二步线性 DP 取答案f[i]前i个数能缩成的最短长度。f[0] 0。枚举最后一段[j1,i]若它能整体缩成一个数即best[j1][i] ! -1f[i] min(f[i], f[j] 1)。答案f[n]。复杂度时间O(n^3)空间O(n^2)。易错点贪心从左到右能合就合不正确。必须区间 DP 判定哪些段能整体缩成一个数。第二章小结消除类靠“相同端点共享操作”省次数匹配/文法类先分清“块”与“序列”用唯一的“第一个块”分解以保证不重不漏再用前缀和压维。第三章 区间最值与构造本章两类① 区间归属/最值按顺序把元素放到当前区间左端或右端状态随两端扩展。② 构造与判定枚举区间的“根”左右成为两棵独立子结构。计数时问自己操作顺序不同算不算不同答案。7. CF1509C The Sports Festival考点排序、从两端扩展、当前极差作为代价。状态定义先把所有数升序排列为a[1..n]。dp[l][r]已安排好恰好是排序后区间[l,r]时之前各轮惩罚之和的最小值。为什么可以假设已安排的是连续区间存在最优顺序使任意时刻已安排的数在排序后都是一段连续区间。下一个加入的数若与当前区间不相邻先安排中间那个数不会更差。转移推导区间[l,r]的最后一轮惩罚恒为a[r] - a[l]。它由[l1,r]刚加入a[l]或[l,r-1]刚加入a[r]扩展而来dp[l][r] (a[r] - a[l]) min(dp[l1][r], dp[l][r-1])。边界dp[i][i] 0。答案dp[1][n]。复杂度时间O(n^2)空间O(n^2)排序O(n log n)。易错点必须先排序代价每一层都要加不是最后加一次累加用long long。8. ABC217 F - Make Pair考点区间配对计数 组合数。题面关键2N 人排成一列每次选相邻且友好的两人配对退出退出后队列合拢。求使所有人配对完成的操作方法数。操作顺序不同算不同答案。状态定义dp[l][r]把偶数长度区间[l,r]内所有人全部配对退出的方法数。空区间l r恰有 1 种方式。转移推导考虑最左端学生l枚举与其配对的人k。中间[l1,k-1]必须先全部配对l、k才能相邻配对右侧[k1,r]独立配对。由奇偶性k只能取l1, l3, ...。基础形式dp[l][r] Σ good[l][k] * dp[l1][k-1] * dp[k1][r] * 组合数。为什么有组合数题目统计的是“每一轮选哪一对”的操作序列。含l的这一组共需a (k-l1)/2次操作右侧一组共需b次操作。两组操作可以任意交错交错方式有C(ab, a)种。所以dp[l][r] Σ good[l][k] * dp[l1][k-1] * dp[k1][r] * C(len/2, (k-l1)/2)。复杂度时间O(n^3)组合数预处理O(n^2)空间O(n^2)。易错点别漏组合数。若只问“配对方式”而不问“操作先后”才可能不乘。只枚举与l奇偶匹配的k步长 2。空区间不能写负下标用l r判定返回 1。9. CF1025D Recovering BST考点枚举根的构造判定、BST 中序有序、gcd 判定。状态定义BST 的中序遍历就是升序序列所以区间[l,r]天然对应一棵子树。难点是某区间作为子树时根还要与区间外的父节点相连。定义两个方向L[l][r]区间[l,r]能否整体作为节点r1的左子树。R[l][r]区间[l,r]能否整体作为节点l-1的右子树。空段视为可行。转移推导枚举区间根k左右两段[l,k-1]、[k1,r]需分别可行inner L[l][k-1] R[k1][r]。若inner成立若r1存在且gcd(a[k], a[r1]) 1则L[l][r] true若l-1存在且gcd(a[k], a[l-1]) 1则R[l][r] true。最后枚举整树根k若L[1][k-1] R[k1][n]则答案 Yes。复杂度时间O(n^3)空间O(n^2)。易错点不能只记区间自身可行因为连边约束来自区间外。空段要单独置为可行。10. TTPC2024 E ReTravel考点路径树、区间枚举根、曼哈顿距离。状态定义路径要回溯整体形成一棵只能向上或向右生长的二叉树按给定访问顺序做 DFS。f[l][r]区间[l,r]对应子树的最小代价。root[l][r]该子树的根。对区间[l,r]根一定取(min x, min y)。转移推导把区间在k处分成两棵子树。两棵子树的根确定后合并根取两子树根的(min x, min y)。代价f[l][k] f[k1][r] dist(root[l][k], rt) dist(root[k1][r], rt)。叶子代价为 0。最终答案还要额外加根到原点(0,0)的曼哈顿距离。复杂度时间O(n^3)空间O(n^2)。易错点别忘了最后加根到原点的距离。坐标到1e9用long long。11. ABC163 E Active Infants考点权排序、区间归属、大权先放端点。状态定义结论活泼度越大的幼儿越应先安排且只放在当前序列的最左端或最右端。把幼儿按活泼度降序排列依次放置。dp[l][r]当前还剩空位区间[l,r]、从当前幼儿开始放的最大贡献。状态依赖“再放一个人之后”空位少 1的状态所以幼儿顺序要倒序计算。转移推导当前幼儿活泼度w原位置pos放左端w * |pos - l| dp[l1][r]放右端w * |pos - r| dp[l][r-1]。所以dp[l][r] max(w * |pos-l| dp[l1][r], w * |pos-r| dp[l][r-1])。空段贡献为 0。答案dp[0][n-1]。复杂度时间O(n^2)空间O(n^2)。易错点按权降序放置但计算dp时要倒序遍历这些人。顺序写反会得到明显偏小答案。乘积与累加用long long。第三章小结区间归属类先排序按“大权优先占端点”从两端扩展构造判定类枚举区间根左右独立。计数时判断操作顺序是否算不同答案——算就乘交错组合数。第四章 区间 DP 优化进阶四边形不等式朴素区间 DP 枚举分割点是O(n^3)。当转移满足区间包含单调性 四边形不等式时最优分割点单调可用决策点区间把枚举压到O(n^2)。12. P4767 [IOI2000] 邮局考点中位数代价、前缀和O(1)求w、决策点单调。题面关键数轴上有n个村庄选m个位置建邮局使每个村庄到最近邮局距离之和最小。第一步一段村庄配一个邮局的代价最优结构里每个邮局负责一段连续的村庄。对一段[l,r]只建一个邮局邮局放在中位数a[mid]mid (lr)/2时代价最小。w(l,r) Σ |a[i] - a[mid]|。用前缀和可O(1)求左半 a[mid] * (mid-l1) - (pre[mid] - pre[l-1])右半 (pre[r] - pre[mid]) - a[mid] * (r-mid)w 左半 右半。第二步朴素区间划分 DPf[k][i]前i个村庄建k个邮局的最小代价。f[k][i] min(f[k-1][j] w(j1,i))其中j从k-1到i-1。f[0][0] 0其余正无穷。答案f[m][n]。第三步决策点单调优化记opt[k][i]为使f[k][i]最小的分割点j。对本问题可证明opt[k-1][i] ≤ opt[k][i] ≤ opt[k][i1]。固定k让i从n递减到k。计算f[k][i]时只需在lo max(k-1, opt[k-1][i])hi (i n ? i-1 : opt[k][i1])之间枚举j。哨兵k 1时lo 0i n时hi i-1。这样总复杂度降到O(n^2)量级。复杂度朴素O(n^2 m)。优化O(n^2)量级空间O(nm)或滚动数组。易错点中位数下标用(lr)/2。优化版i必须倒序否则opt[k][i1]还是 0上界错误。两个哨兵不能少。决策单调性依赖w满足四边形不等式不能乱用。w与f都用long long。附录附录 AP2679 子串为什么不是区间 DP题意从字符串 A 中取出k个互不重叠的非空子串首尾相接恰好等于 B求方案数。常见状态f[k][i][j]表示用了k段、A 处理到i、B 匹配到j再配“当前是否正在延续同一段”的状态或前缀和优化。为什么不是区间 DP区间 DP 的核心是对单个连续区间[l,r]用分割点或两端做转移。本题状态横跨两个序列的位置i,j和已选段数k转移关注字符匹配与“新开一段还是延续上一段”并不存在对某一段内部枚举分割点。它属于双序列子序列/子串计数DP。快速判断状态能否用“一段连续下标[l,r]”刻画且答案由这段的子区间拼出能 → 区间 DP若必须同时跟踪两条序列游标或额外维度通常不是。附录 B区间 DP 方法速查表转移形态结构特征典型题线性合并枚举分割点左右两段合并代价与端点有关P1063、P3146、CF1312E消除匹配相同/可匹配端点可顺带处理文法分块与序列CF1132F、P7914、P4290区间归属按权或顺序把元素放到当前区间左端或右端CF1509C、ABC163E构造判定枚举区间根左右成为独立子结构CF1025D、TTPC2024E方案计数枚举端点配对 乘法原理注意是否乘操作次序组合数ABC217F、P7914四边形不等式优化w满足单调/不等式决策点单调用opt边界压缩枚举P4767附录 C刷题顺序总览编号题目例/练难度核心考点1P1063 能量项链例题easy环形破环为链、枚举分割点2P3146 248例题easy区间相等才能合并、可达值3P7914 超级括号序列例题重点hard文法分块、不重不漏、前缀和4CF1132F Clear the String例题hard同端点顺带删除5P4290 玩具取名练习题medium变形规则、区间可达性6CF1312E Array Shrinking练习题hard区间判定 线性 DP7CF1509C Sports Festival例题hard排序、区间两端扩展8ABC217F Make Pair例题medium配对计数 组合数9CF1025D Recovering BST练习题hard枚举根、gcd 判定10TTPC2024 E ReTravel练习题hard路径树、曼哈顿、区间根11ABC163E Active Infants练习题hard权排序、区间归属12P4767 邮局例题hard中位数代价、四边形不等式建议刷法第 1、2 题打底第 3 题反复啃透4–6 练消除与判定7–11 练归属与构造最后用第 12 题掌握优化。每做一道先自己写状态与转移再对照本手册。