转载自巨佬MashiroSky的博客

数

　　相信有心想学习斜率优化的同志们一定自己摸索着写过[hnoi2008]玩具装箱这道题吧，我刚开始学习斜率优化的时候，也是写了这个，然后似懂非懂的发现，好像斜率优化就是先证明决策单调性，然后再用单调队列维护一下什么的，这不就是套个模板的东西吗→_→。

　　对于某一类型的dp方程

f [i] = M i n (a [i] * b [j] + c [j] + d [i])

　　其中 $a [x], b [x], c [x], d [x]$

　　按照一贯的套路，先数学归纳法证明决策单调性。

　　1.归纳假设：

　　　　假设有 $i$

a [i] * b [j] + c [j] + d [i] >= a [i] * b [k] + c [k] + d [i] ， j < k

　　2.归纳推理：

　　　　此时后面有状态 $i + 1$

即 证 ： a [i + 1] * b [j] + c [j] + d [i + 1] >= a [i + 1] * b [k] +

(a [i] - v) * b [j] + c [j] + d [i + 1] >= (a [i] - v) * b [k] + c [k] +

化 简 得 ： a [i] * b [j] + v * b [k] + c [j] >= a [i] * b [k] + v

由 【 2 】 得 ： a [i] * b [j] + c [j] >= a [i] * b [k] + c [k]

由 【 1 】 得 ： b [k] > b [j]

又 ∵ v > 0

∴ v * b [k] >= v * b [j]

得 证

　　所以，决策单调性是存在的。我们将由决策单调性得出的式子展开，化成斜率式：

a [i] * b [j] + c [j] + d [i] >= a [i] * b [k] + c [k] + d [i] ， j < k

- a [i] >= c [ k ] - c [ j ] b [ k ] - b [ j ]

　　记斜率

s l o p e (i, j) = c [ k ] - c [ j ] b [ k ] - b [ j ]

　　然后发现这个东西很符合单调队列的尿性：

　　问题就这样优化到了 $O (n)$

　　回顾一下我们之所以可以使用斜率优化，是因为这个dp方程具有决策单调性；否则我们推不出斜率式。之后我们将决策单调性的式子变形为斜率式，当满足斜率式的时候就表明前一个决策不如后一个决策优，一切都是围绕着决策单调性开展的，可以说决策单调性是斜率优化的前提。（那是真的么，欲知后事，请看下文）

　　现在我们换一个角度来考虑问题，刚刚是直接从”数“的角度进行了严谨的证明，那么我们现在从”形“的角度来意会。

　　dp方程：

f [i] = M i n (a [i] * b [j] + c [j] + d [i]) ， b [j] 单 增

　　我们这里沿用上面“数”的条件： $a$

　　移项：

- a [i] * b [j] + f [i] = c [j] + d [i]

　　是不是很像直线的斜截式： $- a [i]$

　　可以看出，因为 $f [i]$

　　我们用一个单调队列维护这个凸壳，因为要保证凸壳的下凸性，所以我们显然可以得到单调队列pop队尾的条件： $s l o p e (q [r - 1], q [r]) > s l o p e (q [r], i)$

　　考虑什么情况下pop队首元素（这里我们的讨论都是基于 $f [i]$

　　不错，你一定已经发现第一种情况所对应的维护方式不是跟之前所说“数”的单调队列维护方式一模一样吗，没错，其实这只是两种不同的解题方式所得出来的同样的结果。

　　两种方法各有优缺点吧，“形”的角度比较方便理解，对于更高深的cdq分治维护凸包可以比较清晰的了解。但是遇到复杂的dp方程以及决策单调性证明就得靠“数”了（比如国王饮水记），看情况使用吧。

　　之前说的决策单调性是斜率优化的基础这句话其实并不严谨，像这种从图形角度来求解的斜率优化就并没有用到决策单调性。想一想如果能证明决策单调性，那么一定就是对 $a$

　　这就是斜率优化啦。

　　回顾之前斜率优化的运用，它必须要有一个前提条件： $b$

　　答案是可以的，我们需要使用CDQ分治或者splay来解决这个问题。

　　斜率单调暴力移指针
　　斜率不单调二分找答案
　　x坐标单调开单调队列
　　x坐标不单调开平衡树|cdq分治

参考资料：

This passage is made by MashiroSky.