关于斜率优化的一些理解
学习背景
在高一寒假集训的第二期————
裘学姐的dp课，我的脑袋像空壳。认真听讲每一刻，天敌dp把我克。斜率dp星一颗，带我看清路坎坷。用心和它两天磕，最后来这写博客。
但我希望能有一个支点来撬动我空壳般的脑袋
斜率优化用处
在经典dp式：f[i] = min { f[j] + val(i,j) } 中，当多项式val(i,j)中的每一项仅和 i,j 中的一个有关时，我们可以使用单调队列优化。
但当val(i,j)包含 i,j 的乘积项时，就应当使用斜率优化。
在接下来的讨论中，以i代表暂时不变的转移目标，也是外层变量；j为一个变量，代表一组转移源，也是内层变量。
斜率优化的具体实现
当我们省去经典dp式中的min或max,把它看成一个关于i和常量的式子为参数，关于j的式子为变量的函数式，并转换到形如y=kx+b。b中通常有f[i]和一些常量（关于i的式子看作不变量），所以我们就是求截距b的最小值。
关于j的式子在x,y中，所以我们可以把一组待选的j放到坐标系里面，其中一个在关于i的斜率下，能取到最小的截距，这个j一定在一个凸壳上。
解题步骤大概可以分为如下几步：
-
好好体会题意，判断是否会形成与斜率优化有关的一些东西，比如单调性和dp式子中是否有乘积项。
-
推出这道题的暴力dp，大概思想有推不出来就加一层循环，尽量减少dp数组维度，思维可以简单暴力。
-
将暴力dp化简到最简单的形式，推出斜率优化式。
-
斜率优化的数据结构。如：单调队列（适用于斜率有单调性），二分查找单调栈（适用于x坐标有单调性），平衡树和CDQ分治（适用于x坐标都不单调，实现动态开点和动态插入以及相关维护）。——前面几种简单的适用情况，会在后面详细讲到。
斜率优化式
先有两道例题，都叫任务安排，是在洛谷P2365和P5785（在某知名蓝皮书上也有详细的提及），是最经典的一类斜率优化dp题。
通过它们，我们可以总结出斜率优化式如下原则：
-
基本形式为y=kx+b，b，k中通常是关于常量和 i。y和x中通常关于 j。
-
推导优化式时，最好能在1原则保证的前提下，尽量将式子中的k和x变为有单调性的两个量。斜率优化的具体复杂度，也与它们两个的单调性密切相关。
-
推导优化式有些小技巧——关于 i变量与j变量 或 常量与j变量的式子，把它们转化为kx。——关于j变量但变换上下浮动不定的式子，可以把它转化成y（y很多时候是一个多项式）。——关于i和其他常量放在d中。
-
斜率最好不要有正负的变化（有也可以做）。如洛谷题P3159玩具装箱中很容易推出一个k值有正负变换的式子，很容易可以把它转化为k值单调的式子，大大降低代码思维难度。
维护并快速查找坐标系中最优的j值。
当 k值和x值都单调 时
用单调队列（这里的单调是指队列中各点的斜率单调，即形成一个凸壳）。实现有三步：
- 对于当前的i形成的斜率，从队头开始循环检查，不满足凸的性质的元素出队。
- f[i]从队头的 j 直接转移（因为第一步将此时斜率所切的凸点踢到了队头）。
- 新转移成的f[i]循环检查是否满足凸的性质，不满足则从队尾3踢出，踢到满足后将f[i]入队。
仅当 k值单调 时
用单调栈+二分查找。实现和上方相比，省去了第一步（因为现在i形成的k值不定，我们必须维护整个凸壳）。第二步稍有变化：
因为栈中元素形成的斜率单调，故二分转换时用mid与mid+1元素的斜率与i的斜率作比较来转移 r , l ;(要时刻注意边界，可以通过代入小数据的方法来检查边界)。
然后就结束了
上面的总结显然是有很多局限性和很多不全面的地方。希望在今后的学习中可以将这篇总结加以修订。自勉!