斜率优化

参考资料

• 斜率优化 - OI Wiki

简介

当 DP 转移形如 $f_i=\min_j\set{f_j+w(i,j)}$，且把含 $j$ 的项整理后能写成「关于某个随 $i$ 单调的斜率的一次函数」时，可用 斜率优化。

把每个决策 $j$ 看作平面上一个点，最优转移等价于在这些点构成的 下凸壳 上找到与给定斜率相切的点。当斜率与横坐标都单调时用单调队列维护凸壳，均摊 $O(1)$ 转移，总复杂度降到 $O(n)$；否则可在凸壳上二分。

例题

洛谷 P3195 [HNOI2008] 玩具装箱

$n$ 个玩具排成一列，第 $i$ 个长 $C_i$。将其划分为若干连续段，每段装入一个一维容器，相邻玩具间留 $1$ 单位间隔，则段 $[i,j]$ 的容器长为 $j-i+\sum_{k=i}^{j}C_k$，费用为该长度与 $L$ 之差的平方。求最小总费用。