斜率优化
作用：
将某些复杂度不对的dp方程降一个维度，譬如O（n^2）的dp方程，若其满足决策单调性，既可通过斜率优化对其进行降维打击，让它强行变成O（n）的。
决策单调性：
若对于(f_i)来说，选择k这个决策是最优的，那么对于(f_{i+1})到(f_n)来说，选择k之前的决策不会比选择k更优。例如：若f具有决策单调性(f_{i+1})的决策一定是k或在k后面的决策。
【证明决策单调性】：
【数学归纳法】：
- 设(f_i=min(f_j+a_i-a_j))
- 假设有两个决策j和k,k>j且k优于j
- (f_k+a_i-a_k<f_j+a_i-a_j)
- (f_k-a_k<f_j-a_j)
- 那么对于(f_{i+1})来说选择(k)即(f_{i+1}=f_k+a_{i+1}-a_k)
- 而选择(j)的话即(f_{i+1}=f_j+a_{i+1}-a_j)
- 因为第(4)行的式子，对于(f_{i+1})选择k明显比选择j更优，同理(f_i+2)可通过(f_{i+1})得到，那么，可既可说这个dp方程具有决策单调性。
斜率优化：
举例子说明总是比较直观的，下面我们来看一道例题。
(【)题目(】:)
现在我们有一个序列(a)，我们能把序列(a)切成若干段，对于在(i)和(j)被断开的一段序列，既(a_i..j)，我们可以得到一个分数((sum_{k=i}^ja_k)^2)。我们在i位置切割一次，就会得到(c_i)的分数。那么对于整个序列a，我们希望它的总分最小，求这个分数和。
【(n^2)做法】:
显然，我们能得到一个效率为(n^2)的dp方程
我们先设
[sum_k=sum_{i=1}^ka_i]
[f_i=min(f_j+(sum_i-sum_j)^2+c_i)]
若(nleq10^5)那么这个复杂度不能令人满意，我们就要接着对他进行一些处理。
【证明决策单调性】
若(k> j)且(k)优于(j)
[f_j+(sum_i-sum_j)^2+c_i>f_k+(sum_i-sum_k)^2+c_i]
[f_j+sum_i^2-2times sum_itimes sum_j+sum_j^2+c_i>f_k+sum_i^2-2times sum_itimes sum_k+sum_k^2+c_i]
[f_j-2times sum_itimes sum_j+sum_j^2>f_k-2times sum_i*sum_k+sum_k^2]
那么对于(f_{{i+1}})来说:
选择j为决策既：(f_{{i+1}}=f_j+(sum_{i+1}-sum_j)^2+c_{i+1})
选择k为决策既：(f_{i+1}=f_k+(sum_{i+1}-sum_k)^2+c_{i+1})
从上面的式子可以得到选择k优于选择j（不信的话可以自己展开）
那么可以证明这个dp方程式具有决策单调性的。
【推导斜率式】
[f_j-2times sum_itimes sum_j+sum_j^2>f_k-2times sum_i*sum_k+sum_k^2]
从这条式子继续
[f_j-f_k+sum_j^2-sum_k^2>2times sum_i*(sum_j-sum_k)]
[frac{f_j-f_k+sum_j^2-sum_k^2}{sum_j-sum_k}>2*sum_i]
根据这条式子的定义，我们可以得到，对于(k>j)，只有在满足上面式子的情况下才会k比j优
我们把((f_j+sum_j^2,sum_j))和((f_k+sum_k^2,sum_k))分别看做坐标系上面的点，那么小于号左边的式子的含义恰好是这两个点之间的斜率。
现在我们假设找到了一个点(x,y)对于(f_i)最优。我们在x点上画一条斜率为(2*sum_i)的斜线，那么，对于其他所有点，都必须在这条斜线上方。
证明：若((a,b))在斜线下方，且(a<x)那么根据上面的式子((a,b)(x,y))之间的斜率会大于(2times sum_i)并且(a<x)，那么(x,y)则不是最优点。若(a,b)在斜线下方，且(a>x)那么根据上面的式子((a,b)(x,y))之间的斜率会小于(2times sum_i)并且(a>x)，那么(x,y)则不是最优点。
换句话说，对于(f_i)来说，最优解x是斜率(k=2*sum_i)从下往上扫扫到点集里最优的那个点。
显然，我们可以得到一个很显然的结论，那就是这个最优解x在下凸壳上。那么我们可以通过一个队列来维护凸包，并且根据决策单调性，还有(frac{f_j-f_k+sum_j^2-sum_k^2}{sum_j-sum_k}>2*sum_i)这条斜率式，我们可以每次比对下凸壳上相邻的两个点（也就是队首元素），若队列中第二个元素比队首元素优，那么我们可以删除队首元素（决策单调性，队首元素再也用不到）。
我们注意到，对于点i来说，他的横坐标是(sum_i),因为(sum_i)是前缀和，是递增的，所以加入的点的横坐标也是递增的，那么对于每个点，我们只要把它加入维护凸包的那个队列就好了。
【某些不得不说的东西】：
最后我们推出来的式子一般都是长这样：
(frac{上边一些与j和k相关的元素}{下边一些与j和k相关的递增的元素，注意，是递增}<或>只与i有关并且递增的常数)
如果右边的与i有关的常数不是递增的，那意味着我们要扫的答案的斜率不是递增的，那么决策单调性就会消失，我们就要用平衡树或者三分去维护。所以一般，正常，好写的斜率优化最后推出来的式子一般都形如上面那条√
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
