OI-wiki 斜率优化 DP 完全指南：从玩具装箱到凸包、CDQ 分治与平衡树-育师

OI-wiki 斜率优化 DP 完全指南：从玩具装箱到凸包、CDQ 分治与平衡树

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

斜率优化（Convex Hull Trick，CHT）是动态规划中一类极具代表性的优化技术：它将形如 $f_i=\min_{j<i}{f_j+w(i,j)}$ 的转移方程，通过代数变换转化为二维平面上"用直线切凸包求最小截距"的几何问题，从而把 $O(n^2)$ 的朴素 DP 降到 $O(n)$。本文以 OI-wiki 仓库 docs/dp/opt/slope.md 为骨架，以「HNOI2008 玩具装箱」为主线，完整推导斜率优化的建模过程与凸包维护细节，并深入讲解当斜率单调性、横坐标单调性缺失时，如何用二分、平衡树与 CDQ 分治（CDQ 分治）进行推广。读完本文，你将掌握：如何把任意 $O(n^2)$ 的 1D/1D 转移方程改写为"截距最值"形式；如何用单调队列维护下凸壳并均摊 $O(1)$ 求解；以及斜率不单调时 $O(n\log^2 n)$ 的 CDQ 分治做法。

例题引入：HNOI2008 玩具装箱

有 $n$ 个玩具排成一排，第 $i$ 个玩具价值为 $c_i$，要求将这 $n$ 个玩具分成若干段。对于一段 $[l,r]$，它的代价为

$$ (r-l+\sum_{i=l}^r c_i-L)^2 $$

其中 $L$ 是常量，求分段的最小代价。数据范围为 $1\le n\le 5\times 10^4,\ 1\le L,c_i\le 10^7$。

这个数据规模直接否决了 $O(n^2)$ 的朴素做法，而平方项的存在又提示我们：展开后会出现 $i\cdot j$ 的交叉项，这正是斜率优化（CHT）的典型信号。

朴素 DP 做法

令 $f_i$ 表示前 $i$ 个物品分若干段的最小代价，枚举最后一段的起点 $j+1$，则有状态转移方程：

$$ f_i=\min_{j<i}{f_j+(i-(j+1)+pre_i-pre_j-L)^2}=\min_{j<i}{f_j+(pre_i-pre_j+i-j-1-L)^2} $$

其中 $pre_i=\sum_{k=1}^{i}c_k$ 是前缀和。由于每次转移需要枚举全部 $j<i$，朴素实现的时间复杂度为 $O(n^2)$，在 $n=5\times10^4$ 时无法承受。

简化转移方程

观察括号内的项 $pre_i-pre_j+i-j-1-L$，可以令

$$ s_i=pre_i+i,\qquad L'=L+1 $$

于是转移方程简化为

$$ f_i=\min_{j<i}{f_j+(s_i-s_j-L')^2} $$

几何建模：把 DP 化成截距最值问题

将平方展开，并把与 $j$ 无关的项移到 $\min$ 外：

$$ f_i-(s_i-L')^2=\min_{j<i}{f_j+s_j^2+2s_j(L'-s_i)} $$

回忆一次函数的斜截式 $y=kx+b$，移项得到 $b=y-kx$。我们做如下对应：把与 $j$（决策点）有关的信息放进 $y$，把同时与 $i,j$ 有关的信息放进 $kx$，把与 $i$ 有关、需要最小化的信息放进 $b$（截距）。具体地，设

$$ \begin{aligned} x_j&=s_j\ y_j&=f_j+s_j^2\ k_i&=-2(L'-s_i)\ b_i&=f_i-(s_i-L')^2 \end{aligned} $$

则转移方程写作

$$ b_i=\min_{j<i}{y_j-k_ix_j} $$

此时 $(x_j,y_j)$ 是二维平面上的点，$k_i$ 是直线斜率，$b_i$ 是"过点 $(x_j,y_j)$、斜率为 $k_i$ 的直线"在 $y$ 轴上的截距。原问题就此转化为：在已有决策点集中，选择点 $j$，使过该点、斜率为 $k_i$ 的直线截距最小。

如上图（docs/dp/images/optimization.svg），将斜率为 $k_i$ 的直线从下往上平移，直到某个点 $(x_p,y_p)$ 落在直线上，此时 $b_i=y_p-k_ix_p$ 取到最小值。算完 $f_i$ 后，把新点 $(x_i,y_i)$ 加入点集，作为后续转移的候选决策。

为什么只需维护下凸壳

容易发现，能使 $b_i$ 取到最小值的点一定落在下凸壳上：位于凸包内部的点，无论直线斜率如何，都不可能最先被切到。因此寻找 $p$ 时无需枚举全部 $i-1$ 个点，只需考察凸包顶点。更进一步，在本题中 $k_i$ 随 $i$ 递增而单调递增，于是可以用单调队列维护凸包，配合队首指针实现均摊 $O(1)$ 的查询。

单调队列维护下凸壳

记 $K(a,b)$ 为过点 $(x_a,y_a)$ 与 $(x_b,y_b)$ 的直线斜率。队列 $q_l,q_{l+1},\ldots,q_r$ 维护的是下凸壳上的点，即对任意 $l<i<r$，始终有

$$ K(q_{i-1},q_i)<K(q_i,q_{i+1}) $$

也就是说，凸壳上相邻点的斜率严格递增，这正是后续二分的基础。

查询：用直线切凸壳

维护一个指针 $e$，寻找满足

$$ K(q_{e-1},q_e)\le k_i < K(q_e,q_{e+1}) $$

的 $e$（当 $e=l$ 或 $e=r$ 时做边界特判），此时 $p=q_e$ 即为最优决策点。由于 $k_i$ 单调递增，$e$ 只会向右移动，总移动次数均摊 $O(1)$。

插入：维护凸性

插入新点 $(x_i,y_i)$ 时，先判断

$$ K(q_{r-1},q_r)<K(q_r,i) $$

若不等式不成立，说明 $q_r$ 已不可能再成为凸壳顶点，将其从队尾弹出，重复直到不等式成立，再把 $i$ 入队。这保证了新点加入后队列依然满足"相邻斜率严格递增"的凸性条件。

至此，DP 的复杂度从 $O(n^2)$ 优化到了 $O(n)$。

算法流程概括

将初始状态（边界点）入队。
对每个 $i$，使用与 $i$ 相关的直线 $f(i)$ 去切维护的凸包，找到最优决策点，更新 $dp_i$。
加入状态 $dp_i$：若某状态在 $dp_i$ 加入后不再是凸包上的点，需在入队前将其剔除。

斜率优化的适用范围不限于玩具装箱，同一框架（变换 → 建点 → 维护凸壳 → 直线切凸壳）可推广到大量带平方代价或交叉项的 1D/1D DP，例如后文习题中的仓库建设、特别行动队、货币兑换等经典问题。

进阶：当单调性缺失——二分、平衡树与 CDQ 分治

上面之所以能用单调队列，依赖两个关键性质：

查询时，直线的斜率 $k_i$ 随 $i$ 单调变化；
插入时，决策点的横坐标 $x_j=s_j$ 单调递增。

玩具装箱改：价值可以为负

考虑「玩具装箱」的变体：唯一区别是玩具价值可以为负，即 $1\le n\le 5\times10^4,\ 1\le L\le 10^7,\ -10^7\le c_i\le 10^7$。

沿用之前的定义，令 $f_i$ 表示前 $i$ 个物品分段的最小代价，转移方程为

$$ f_i=\min_{j<i}{f_j+(pre_i-pre_j+i-j-1-L)^2} $$

做相同的变换后得到

$$ f_i-(s_i-L')^2=\min_{j<i}{f_j+s_j^2+2s_j(L'-s_i)} $$

然而此时两个条件都不再成立：

直线的斜率不再单调：$c_i$ 可为负导致 $s_i$ 不单调，进而 $k_i=-2(L'-s_i)$ 不单调，队首指针 $e$ 无法只向右移动；
决策点的横坐标不再单调：$x_j=s_j$ 不单调，新点可能插入到凸壳中间，无法简单地从队尾入队。

但凸壳本身仍然存在，问题变为"如何在不单调的两种意义下维护和查询凸壳"。

查询端：凸壳上二分

在寻找最优决策、即用直线切凸壳时，把"单调队列找队首"改为"在凸壳上二分"：由于凸壳上相邻两点的斜率 $K(q_{i-1},q_i)$ 具有单调性，可以二分出斜率最接近 $k_i$ 的那条凸壳边，其端点即为最优决策。二分将单次查询从均摊 $O(1)$ 变为 $O(\log n)$。

插入端：两种维护方案

方案一：平衡树维护凸壳。用平衡树直接维护凸壳上的点，查询决策点时在平衡树上二分，插入决策点时在平衡树上插入结点并删除若干被踢出凸壳的点。此方法思路简洁，但实现繁琐（需要维护前驱后继斜率关系）。

方案二：CDQ 分治（推荐）。OI-wiki 在 docs/misc/cdq-divide.md 中系统介绍了 CDQ 分治，并将其列为三类主要应用之一：1D 动态规划的优化与转移。下面展开基于 CDQ 分治的斜率优化做法。

CDQ 分治优化斜率 DP

设 $\text{CDQ}(l,r)$ 负责计算 $f_i,\ i\in[l,r]$。考虑 $\text{CDQ}(1,n)$ 的流程：

先调用 $\text{CDQ}(1,mid)$ 算出 $f_i,\ i\in[1,mid]$；
对 $[1,mid]$ 内的决策点（此时全部已算毕）静态建凸壳，用这个凸壳去更新 $f_i,\ i\in[mid+1,n]$；
由于此时决策点集固定不变（不像原问题边算 DP 边加决策点），可以把 $i\in[mid+1,n]$ 的 $f_i$ 按直线斜率 $k_i$ 排序，再用单调队列计算 DP 值；当然也可以在静态凸壳上二分计算；
对 $[mid+1,n]$ 中的每个点，若其最优决策恰在 $[1,mid]$，则在这一步就被更新成最优答案。执行完这一步后，$[1,mid]$ 中的点已发挥全部作用，可以整体舍弃该区间，递归调用 $\text{CDQ}(mid+1,n)$ 解决右区间剩下的问题。

每次合并的复杂度为 $O(n\log n)$（排序或建凸壳），总时间复杂度为 $O(n\log^2 n)$。

为什么 CDQ 能正确处理

CDQ 分治优化 DP 与处理点对问题的 CDQ 写法有一个关键差异：转移必须夹在两次递归之间（先solve(l,mid)，再处理跨区间转移，最后solve(mid+1,r)），因为 DP 转移是有序的，必须满足两个条件：

用来计算 $f_i$ 的所有 $f_j$ 都必须已计算完毕，不能存在"半成品"；
用来计算 $f_i$ 的所有 $f_j$ 都必须能更新到 $f_i$，不能有漏更。

在 CDQ 的递归结构下，一个 $i$ 点的 DP 值会被更新 $O(\log n)$ 次，而更新它的区间恰好是 $(1,i)$ 在线段树/分治树上被拆分出的 $O(\log n)$ 个不相交区间。因此所有合法的 $j<i$ 都恰好覆盖了 $i$，正确性得以保证。关于该递归树结构与正确性证明的完整讨论，可参见 docs/misc/cdq-divide.md 中的「CDQ 分治优化 1D/1D 动态规划的转移」一节。

两种思路的对比小结

对比「玩具装箱」与「玩具装箱改」，可以总结出两点方法论：

二分、CDQ、平衡树等工具能够优化 DP 方程的计算，在一定程度降低复杂度，但不能改变方程本身；
DP 方程的性质（斜率是否单调、横坐标是否单调）取决于数据的特征，而 DP 方程本身取决于题目中的数学模型。做题时应先建立模型，再根据数据特征选择合适的凸壳维护与查询手段。