那天下午我被一道平台练习赛的G题卡了快一个小时，题目名就俩字：“分割”。题意一句话能说清：给一个长度为n的数组，把它切成任意段连续子段，每一段的代价是段内最大值，问整个数组切完之后的最小总代价是多少。n的上限是2e5，看到这个数据范围，暴力O(n^2) DP肯定没戏，但一时半会儿又找不到好的优化方向。事后复盘，这道题其实是一个非常经典的“单调栈 + 线段树维护DP候选值”的组合模型，思路通了之后代码并不长，关键是要理解清楚每个优化步骤在干什么。

这篇文章我会按我当时从暴力到AC的思考顺序来写：先讲最朴素的DP，再讲为什么能用单调栈把后缀最大值分段，以及线段树怎么配合区间加和查询最小值，最后贴出可以直接抄的完整代码，顺手总结几个我踩过的坑。如果你正在刷动态规划优化，或者对“线段树维护可变的区间贡献”这类套路不太熟，这篇应该能帮你省不少时间。

1. 题目理解与暴力解法

1.1 先把题目翻译成人话

给定长度为n的数组a[1..n]，你要把它切成若干个连续段，比如[l1, r1], [l2, r2], ..., [lm, rm]，要求这些段按顺序拼起来正好覆盖整个数组。每一段的代价是这一段里的最大值，总代价是所有段代价之和，目标是让总代价最小。

举个例子，a = [2, 5, 1]。你可以：

• 一整段[2,5,1]，代价是5，总代价5；
• 分成[2] + [5,1]，代价2 + 5 = 7；
• 分成[2,5] + [1]，代价5 + 1 = 6；
• 分成[2] + [5] + [1]，代价2 + 5 + 1 = 8。

最小总代价是5，也就是整个数组不切，让最大值5覆盖掉所有元素。这个例子非常关键，它天然否掉了一种很常见的错误直觉：贪心把每个大值单独切出来。

1.2 暴力DP怎么写

一旦看到“切分成若干段，求最值”，第一反应基本就是区间DP的一维版本。设dp[i]表示把前缀a[1..i]切完的最小总代价，那么我只需要枚举最后一段的起点j+1，于是最后一段是a[j+1..i]，其代价为区间最大值，转移就是：

dp[i] = min(dp[j] + max(a[j+1..i]))，其中 0 ≤ j < i

这里dp[0] = 0，最终答案dp[n]。

为了写暴力代码，区间最大值可以每次用一层循环边走边更新。伪代码如下：

dp[0] = 0 for i = 1 to n: dp[i] = INF curMax = 0 for j = i - 1 downto 0: curMax = max(curMax, a[j + 1]) dp[i] = min(dp[i], dp[j] + curMax)

复杂度是O(n^2)。n = 2000的时候完全没问题，n = 2e5就直接超时了。我当时暴力跑了一遍小样例，确认dp方向没错，接下来要思考的就是：如何加速这个“min(dp[j] + max(...))”。

1.3 贪心为什么不行

在动手写优化之前，我特意花了点时间验证贪心确实不行，省得后面绕弯路。最容易想到的贪心是“把每个局部比较大的值单独切开，因为单独一段的max就是它本身，不会拖累别人”。但看[2,5,1]，如果把5单独切开，代价是2+5+1=8，反而比整段5更差。

原因在于这个代价函数有个反直觉的特性：段内的非最大值元素不会增加任何代价，它们可以“免费蹭”段内最大值的覆盖。所以从最优化的角度，大值覆盖的范围越大，往往越划算，因为可以把周围的小值都带进同一个段里，只需要付一次大值的钱。可是又不能无限覆盖，因为同一段只能有一个max，如果两个大值被强行放在同一段，段代价会变成较大那个，另一个大值相当于也被“带”了，可能不亏，但有时分开放反而让每个大值都只覆盖小值，更省钱。

这本质上是一个“每个元素要么成为某段的max，要么被段内另一个大值带着走”的权衡问题。贪心很难找到全局最优，还是老老实实DP。

2. 优化方向：把每个j的候选值看成“固定部分 + 动态部分”

2.1 从状态转移式中拆出变化量

回到暴力DP的转移式：

dp[i] = min(dp[j] + max(a[j+1..i]))，0 ≤ j < i

对于一个固定的j，dp[j]是已经算好的常量，变化的是max(a[j+1..i])——它随i的增大不断变化。如果我能设计一个数据结构，让每个j始终维护“dp[j] + 当前的后缀最大值”，那么每算完一个dp[i]，我只需要在这个数据结构里查询所有j∈[0, i-1]的最小值。

换句话说，我需要维护一个数组val[j] = dp[j] + max(a[j+1..当前i])，然后不断执行：

• 当i增加到i+1时，新元素a[i+1]会改变一部分val[j]；
• dp[i] = min(val[0..i-1])；
• 之后val[i]需要被初始化成dp[i]，参与到后续的维护中。

这里难点就在第一步：新元素到底会改变哪些j的val值？它只改变那些“旧后缀最大值小于a[i]”的j，因为：

max(a[j+1..i]) = max(max(a[j+1..i-1]), a[i])

如果旧的max已经比a[i]大，那新的max不变；如果旧的max比a[i]小，那就被顶成a[i]。问题是怎么快速找出所有这些j。

2.2 后缀最大值天然可以按段划分

以一个具体数组为例，模拟一下i不断右移时后缀最大值的变化。假设数组是[2, 4, 3, 5]，我们看i=3时不同的左端点j对应的max：

• j=0，区间[1..3]，max=4
• j=1，区间[2..3]，max=4
• j=2，区间[3..3]，max=3

到了i=4，加入a[4]=5之后：

• j=0，区间[1..4]，max=5
• j=1，区间[2..4]，max=5
• j=2，区间[3..4]，max=5
• j=3，区间[4..4]，max=5

可以看到，后缀最大值会“合并成越来越大的段”。在i=3的时候是两段：[0,1]对应值4，[2,2]对应值3；加入5之后，所有段都被5统一覆盖成一段[0,3]对应值5。

这就是单调栈的典型场景：维护若干个连续的j区间[L,R]，使得区间内所有j当前的max(x[j+1..i])都等于同一个值mx，并且从栈底到栈顶，这个mx是严格递减的。为什么递减？因为j越小，区间起点越靠左，能包含的元素越多，最大值只会不变或变大，不可能变小。

当一个新的a[i]到来时，如果栈顶段的mx ≤ a[i]，那说明这个段里所有j的后缀最大值都会被抬升到a[i]。我需要给这些j的val统一加上(a[i] - 旧mx)，然后把这个段合并到新的段里。这个过程一直持续到栈顶段的mx > a[i]为止，最后压入一个由a[i]作为新max的新段。

2.3 线段树承担什么角色

单调栈能告诉我哪些j的val值需要区间加，但不能告诉我“所有j的val最小值是多少”。这正好是线段树的强项：用一棵线段树维护val[j]，支持：

• 区间加：给一段j的val统一加上某个增量
• 区间求最小值：查询[0, i-1]范围内的最小val

于是整个算法的骨架就清楚了。从左到右枚举i=1..n，每轮做三件事：

1. 用单调栈判断a[i]会抬升哪些已有的后缀max段，对这些段在线段树里做区间加；
2. 查询线段树区间[0, i-1]的最小值，得到dp[i]；
3. 把下标i对应的线段树叶子更新为dp[i]，因为未来它作为j时，初始候选值就是dp[i]，之后再由后续元素的后缀max去叠加。

3. 核心维护细节与完整代码

3.1 单调栈节点的区间边界怎么算

写代码的时候最容易出错的就是单调栈节点的区间边界。我参考了很多常见写法，最稳的一种是让每个栈节点存三个东西：

l: 左端点j的下标 r: 右端点j的下标 mx: 这个区间内所有j当前对应的后缀最大值

初始时栈是空的。枚举到i时，先用一个变量pos = i - 1表示“新的段从哪个j下标开始”。然后不断看栈顶：

while 栈不为空 and 栈顶.mx <= a[i]: 对线段树区间 [栈顶.l, 栈顶.r] 区间加 (a[i] - 栈顶.mx) pos = 栈顶.l 弹出栈顶

循环结束后，压入新的节点{pos, i - 1, a[i]}。

我来带一下流程，解释为什么这个写法是对的。当栈顶段的mx ≤ a[i]时，这个段里的每个j，其后缀最大值从旧mx变成了a[i]，所以val[j]要加上差值。加完之后，这些j和新元素a[i]共同组成了新的“最大值为a[i]”的段。由于栈里上一段可能也被抬升，所以合并后的段左端点是那个被弹出的最左边的l，也就是pos。而右端点呢？新节点的r一定是i-1，因为当前枚举到i，左端点j最大只能是i-1。这个区间里的所有j，它们对应的区间右端点都是i，所以后缀最大值都包含a[i]，如果a[i]成为了新的最大，那它们的max全都等于a[i]。

等这个栈更新完之后，线段树里所有j∈[0, i-1]的val[j]就已经全部等于dp[j] + max(a[j+1..i])了。于是dp[i] = query(0, i-1)。

3.2 线段树的两点实现经验

写线段树的时候，我踩了两个小坑，提前说：

第一个是点更新的问题。初始时，除了val[0] = 0，其余val[j]应该都是INF，因为j还在“未来”，不能被当作决策点。等dp[i]算完后，需要把下标i的叶子从INF改成dp[i]，这是点赋值，不是区间加。如果线段树只写了区间加接口，处理起来很别扭。我建议线段树同时提供“单点赋值”或者“点更新”功能，初始化时把所有叶子设为INF。

第二个是区间加的范围问题。所有对val的更新只发生在已经被压入栈的j区间，这些j一定都小于i，所以区间加的操作永远落在[0, i-1]范围内。查询也只在[0, i-1]范围内做，不能把INF叶子查进来。至于下标i，它是这一轮最后才变成合法决策点的，顺序不能反。

3.3 可运行的C++17实现

下面是我整理后的完整代码，已经用小样例和对拍验证过。

#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = (1LL << 60); struct SegTree { int n; vector<ll> mn, lazy; SegTree(int _n) : n(_n), mn(4 * _n + 5, INF), lazy(4 * _n + 5, 0) {} void push(int p) { if (lazy[p] != 0) { mn[p << 1] += lazy[p]; lazy[p << 1] += lazy[p]; mn[p << 1 | 1] += lazy[p]; lazy[p << 1 | 1] += lazy[p]; lazy[p] = 0; } } void pull(int p) { mn[p] = min(mn[p << 1], mn[p << 1 | 1]); } void rangeAdd(int p, int l, int r, int ql, int qr, ll v) { if (ql <= l && r <= qr) { mn[p] += v; lazy[p] += v; return; } push(p); int mid = (l + r) >> 1; if (ql <= mid) rangeAdd(p << 1, l, mid, ql, qr, v); if (qr > mid) rangeAdd(p << 1 | 1, mid + 1, r, ql, qr, v); pull(p); } void pointSet(int p, int l, int r, int pos, ll v) { if (l == r) { mn[p] = v; lazy[p] = 0; return; } push(p); int mid = (l + r) >> 1; if (pos <= mid) pointSet(p << 1, l, mid, pos, v); else pointSet(p << 1 | 1, mid + 1, r, pos, v); pull(p); } ll rangeQuery(int p, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) return mn[p]; push(p); int mid = (l + r) >> 1; ll res = INF; if (ql <= mid) res = min(res, rangeQuery(p << 1, l, mid, ql, qr)); if (qr > mid) res = min(res, rangeQuery(p << 1 | 1, mid + 1, r, ql, qr)); return res; } }; struct StackItem { int l, r; ll mx; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<ll> a(n + 1); for (int i = 1; i <= n; ++i) cin >> a[i]; SegTree seg(n + 1); // 初始：val[0] = dp[0] + max(空后缀) = 0，其余为 INF seg.pointSet(1, 0, n, 0, 0); vector<StackItem> st; vector<ll> dp(n + 1, 0); for (int i = 1; i <= n; ++i) { int pos = i - 1; while (!st.empty() && st.back().mx <= a[i]) { int l = st.back().l; int r = st.back().r; ll oldMx = st.back().mx; seg.rangeAdd(1, 0, n, l, r, a[i] - oldMx); pos = l; st.pop_back(); } st.push_back({pos, i - 1, a[i]}); dp[i] = seg.rangeQuery(1, 0, n, 0, i - 1); // 下标 i 从现在开始成为合法决策点，候选值为 dp[i] seg.pointSet(1, 0, n, i, dp[i]); } cout << dp[n] << "\n"; return 0; }

这个代码的核心逻辑都集中在主循环里。如果你之前没接触过这类套路，我建议不要直接抄完就跑，而是自己把几个小样例在纸上模拟一遍，特别是要搞清楚“pos = st.back().l”到底合并到了什么位置。

4. 正确性验证与复杂度分析

4.1 手跑一个样例验证转移完全等价

拿[3, 1, 2]来验证。按题意，最优解是第一段直接取整段，代价max=3，答案是3。

代码跑的过程：

初始线段树只有val[0]=0，栈空。

i=1，a1=3：

• pos=0，栈空，压入{0,0,3}
• 查询[0,0]得dp1=0+3=3
• 设置val[1]=3。此时栈表示：段[0,0]的后缀max是3，对应区间[1,1]的最大值3。

i=2，a2=1：

• pos=1
• 栈顶{0,0,3}的mx=3 > 1，不弹出
• 压入{1,1,1}
• 查询[0,1]：val[0] = 0 + max(a1..a2) = 3，val[1] = dp1 + max(a2..a2) = 3+1=4，所以dp2=3
• 设置val[2]=3

i=3，a3=2：

• pos=2
• 栈顶{1,1,1}的mx=1 <= 2，给区间[1,1]区间加(2-1)=1，val[1]=4+1=5，pos=1，弹出
• 现在栈顶{0,0,3}的mx=3 > 2，不弹，压入{1,2,2}
• 查询[0,2]：val[0]=3，val[1]=5（dp1+max(a2..a3)=3+2），val[2]=dp2+max(a3)=3+2=5，最小值3，所以dp3=3

答案3，和手算一致。注意这里val[1]之所以变成5，其实对应的是j=1，最后一段是[2,3]，max=2，dp[1]=3，总代价5，但它不是最优。线段树维护过程完全没有丢失信息。

4.2 为什么不会漏掉某个dp[j]的更新

本质原因是：任意时刻，线段树叶子的值就是dp[j] + max(a[j+1..当前i])，这里j覆盖0..i-1。当i右移时，只有max值可能变大，而变大只会发生在旧max ≤ a[i]的j上。这些j在单调栈里恰好被分成了一个一个的连续区间，每个区间内部的max相同，所以我只要按区间做整体加法，就能让所有受影响j的val同步更新到正确值。没受影响的j，它们的max不变，也不需要动。这就是“单调栈分段、线段树批量加”能够保住严格等价性的原因。

4.3 时间复杂度：每个下标最多进栈出栈一次

整个算法的复杂度非常优秀。单调栈部分，每个栈节点最多被压入一次、弹出一次，因此每个i在while里的总次数均摊是O(1)。线段树每次区间加和区间查询都是O(log n)，一共n轮，每轮可能做若干次区间加，但总区间加次数就是总弹出次数加1，仍是O(n)。所以总复杂度O(n log n)，空间O(n)。

真算起来：

• 单调栈操作的均摊复杂度O(n)
• 线段树区间加次数 ≤ 总弹出次数 + n，等于O(n)
• 每次区间加O(log n)，每次查询O(log n)，每次点更新O(log n)
• 合计O(n log n)

这在n=2e5时是非常轻松的。如果你用线段树常数写得不好，也基本在1秒到2秒之间能跑过。

4.4 进阶：如果每段代价是最大值减最小值

这道题如果原题是另一道类似的“每段代价=max-min”的分割题，思路也能扩展。只要把val[j]维护成dp[j] + max(a[j+1..i]) - min(a[j+1..i])，那么就需要同时维护两个单调栈：一个单调递减栈维护后缀最大值，一个单调递增栈维护后缀最小值。新元素a[i]会同时触发“最大值段合并增加”和“最小值段合并减少”。线段树需要支持两次区间加，一次加正的差值，一次加负的差值。

具体来说：

• 用单调递减栈维护“最大值”段，当a[i]大于某段旧mx，对该段加a[i]-旧mx；
• 用单调递增栈维护“最小值”段，当a[i]小于某段旧mn，对该段加a[i]-旧mn（注意这是负增量）。

两个栈各自维护各自的区间，互不干扰，在线段树上的累加是叠加的。这样依然可以O(n log n)解决。代码会比单栈长很多，但核心思想完全是同一个套路。这里先点到为止，真碰到这类题，你能想起“这题能用双栈+线段树维护DP候选值”就已经赢了一半。

5. 常见问题与调试实录

5.1 栈区间边界算错

这是我实际写的时候最容易错的地方。常见的错法是压入新节点时右端点写成i而非i-1。仔细想一下：当前处理到i，左端点j的范围最大只能是i-1，因为最后一段至少要有一个元素a[i]。如果右端点误写成i，相当于把还没设置val[i]的下标也塞进栈里，那等到查询的时候，线段树的这个叶子可能还是INF，或者已经被点更新成了dp[i]，但它的max部分还没被正确初始化，就会污染最小值查询。

调试建议：在每次循环结束时打印栈的内容（每个节点的l、r、mx），以及线段树前几个叶子的值，对照自己手算的dp数组。如果发现栈里出现了r >= i，基本就是边界写错了。

5.2 线段树初始INF和点更新的锅

另一个隐蔽问题是线段树建树时所有叶子是INF，val[0]必须单独设为0。如果你忘了设置val[0]，第一个dp[1]就会被算成INF，后面全乱。而点更新时必须先把下标i的旧值从INF覆盖成dp[i]，不能写成“区间加一个差值”的方式。

我曾经试着用区间加来模拟点更新：

seg.rangeAdd(i, i, dp[i] - INF);

这看起来把INF变成了dp[i]，实际上整数运算没问题，但一旦以后该叶子被区间加，INF风格下可能产生奇怪的大额变化，而且排查起来很费劲。不如老老实实加一个pointSet接口，清晰直观。

5.3 相等元素的处理：用<=还是<

在单调栈弹栈时，我写的是st.back().mx <= a[i]（小于等于就弹出）。这个选择很关键：如果改成<，只弹出严格小于的情况，等于的情况会留在栈里，那么两个相等且相邻的大值会形成两个不同段，查询时取min结果可能还是对的，但复杂度会退化到接近O(n^2)，因为相等的元素可能互相拆散，导致每个新元素都要跟一大串相等元素比较但都不弹出。

取<=的好处是把所有相等或更小的旧段全部合并成一个新段，保证栈里每个mx严格递减，这样每个节点最多弹一次。代价是“以最后一个相等元素作为max代表”，但这不影响正确性，因为价值是mx本身，不是元素位置。

5.4 小数据对拍是救命的

写完之后不要急着交，先写一个O(n^2)的暴力DP，随机生成n≤10的数据对拍。我自己测出来过两处bug：一是线段树点更新位置没有加一，二是查询区间写成[0, i]导致把还没初始化的叶子查进去。这些都是对拍几秒钟就能暴露的问题。

对拍时注意生成的数据要有一定范围的负数吗？这道题数组元素如果是负数，段最大值可能是负数，代价负数意味着切分反而“赚钱”，转移依然成立，但手算容易晕。我建议先保证数据非负，验证逻辑，再考虑负数场景。线段树初始化的INF只要足够大就没事。

最后说一点体会

这类“任意分割 + 段代价只跟区间最值相关”的DP，真正难的地方不是想出dp[i] = min(dp[j] + max(...))，而是意识到可以把每个j的候选值变成一个可动态维护的量。以后你再看到“分割成若干段，段代价是区间max/min/或由端点决定”的题，可以本能地往单调栈维护最值段这个方向想一想。我后来拿这个套路秒过好几道类似题，基本形成条件反射了：先列O(n^2)转移，再把max部分用单调栈分段，最后线段树维护最小值。这套组合拳，值得多练几遍。