斜率优化
原理
平面上 \(n\) 个点 \((x_i, y_i)\)，任意给出 \(a, b\)，则 \(ax_i+by_i\) 的最大值，最小值均在 \(n\) 个点构成的凸包上。
令 \(ax_i+by_i=c\)，转成 \(-by_i=ax_i-c\)，求 \(c\) 的最值。
就是求斜率为 \(a\) 的，经过 \((x_i,-by_i)\) 的 \(y\) 轴上截距取到最值的那个点。
而 \(y\) 坐标乘上 \(b\)，对于一个点是否在凸包上，并不影响。
因此，如果状态转移方程可以写成 \(y=ax+b\) 的形式则可以试用斜率优化。
或者说，假设 dp 转移方程需要枚举一维 \(j\)，并且能通过包括移项等一系列操作化成 \(y(j)=kx(j)+b\)，其中 \(k, b\) 是常数的形式，则可以使用斜率优化.
例子
以 [SDOI2016] 征途 为例，阐述如何实现。
记 \(S_i=\sum_{j=1}^ia_j\)，对于方差式子的转换见这个，得到 \(m\sum_{i=1}^mb_i^2-S_n^2\)
设 \(f(i, j)\) 表示将前 \(i\) 个数分成 \(j\) 段 \(\sum_{k=1}^jb_k^2\) 的最小值，则
这样化成 \(y=kx+b\) 的形式得
这是标准的斜率式 \(y(k) = k\times x(k)+b\)，然后分析维护方式和维护上/下凸包.
因为 \(k,x(k)\) 都是递增的，直接单调队列维护即可。
同时因为 \(f(i,j)\) 在 \(b\) 中为正，要求最小值，所以维护下凸包。
\(k,x(j)\) 的单调性
-
\(k,x(j)\) 都单调：[HNOI2018] 玩具装箱
- 使用单调队列维护。
-
\(k\) 不单调，\(x(j)\) 单调：[SDOI2012]任务安排
- 使用单调队列维护，转移在单调队列上二分
-
\(k,x(j)\) 不单调：[NOI2007] 货币兑换
-
CDQ 分治、李超树维护，推荐。
前者需要离线，但用处更广泛。
后者可以应付强制在线，但如果只能从一个区间转移，比平衡树多一个 \(\log\)
-
分块，在李超树 \(\log^2\) 的情况下，也许可以选择每块维护一个凸包，有时候因为常数问题，两个 \(\log\) 和根号速度差不多。
-
平衡树、set 维护，不太推荐，难写。
-
-
\(k\) 单调，\(x(j)\) 不单调：没见过。
其他习题
YZOJ 1767 [Ceoi2009]harbingers
YZOJ 70107 保护
Slope Trick：解决一类凸代价函数的DP优化问题
当序列 DP 的转移代价函数满足
- 连续；
- 凸函数；
- 分段线性函数.
时，可以通过记录分段函数的最右一段 \(f_r(x)\) 以及其分段点 \(L\) 实现快速维护代价的效果。
如：
可以仅记录 \(f_r(x)=2x-3\) 与分段点 \(L_f=\{-1,-1,1\}\) 来实现对该分段函数的存储。
注意：要求相邻分段点之间函数的斜率差为 \(1\) ，也就是说相邻两段之间斜率差 \(>1\) 的话，这个分段点要在序列里出现多次。
优秀的性质：
\(F(x),G(x)\) 均为满足上述条件的分段线性函数，那么 \(H(x)=F(x)+G(x)\) 同样为满足条件的分段线性函数，且 \(H_r(x)=F_r(x)+G_r(x),L_H=L_F\cup L_G\)。
该性质使得我们可以很方便得运用数据结构维护 \(L\) 序列。