斜率优化学习笔记

斜率优化学习笔记
发现自己傻傻分不清斜率优化和决策单调性→_→，被一些博客误导了。。于是总结一下。萌新们可以先写写[hnoi2008]玩具装箱，并不难。

数

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

　　对于某一类型的dp方程 f[i]=Min(a[i]∗b[j]+c[j]+d[i])$f[i]=Min(a[i]\ast b[j]+c[j]+d[i])$

　　其中a[x],b[x],c[x],d[x]是关于x的函数，且b单增。——————【1】

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

　　1.归纳假设：

　　　　假设有i前两个决策点j,k(j<k)$j,k(j<k)$，且k$k$的决策要比j$j$好，即：
　　　a[i]∗b[j]+c[j]+d[i]>=a[i]∗b[k]+c[k]+d[i]，j<k$a[i]\ast b[j]+c[j]+d[i]>=a[i]\ast b[k]+c[k]+d[i]，j<k$——————【2】

　　2.归纳推理：

　　　　此时后面有状态i+1，这里我们为了简单起见，不妨设a[i+1]=a[i]−v,v>0$a[i+1]=a[i]-v,v>0$，也就是a$a$单调递减。
即证：a[i+1]∗b[j]+c[j]+d[i+1]>=a[i+1]∗b[k]+c[k]+d[i+1]$a[i+1]\ast b[j]+c[j]+d[i+1]>=a[i+1]\ast b[k]+c[k]+d[i+1]$

(a[i]−v)∗b[j]+c[j]+d[i+1]>=(a[i]−v)∗b[k]+c[k]+d[i+1]$(a[i]-v)\ast b[j]+c[j]+d[i+1]>=(a[i]-v)\ast b[k]+c[k]+d[i+1]$

化简得：a[i]∗b[j]+v∗b[k]+c[j]>=a[i]∗b[k]+v∗b[j]+c[k]$a[i]\ast b[j]+v\ast b[k]+c[j]>=a[i]\ast b[k]+v\ast b[j]+c[k]$

由【2】得：a[i]∗b[j]+c[j]>=a[i]∗b[k]+c[k]$a[i]\ast b[j]+c[j]>=a[i]\ast b[k]+c[k]$
由【1】得：b[k]>b[j]$b[k]>b[j]$
又∵v>0$\because v>0$
∴v∗b[k]>=v∗b[j]$\therefore v\ast b[k]>=v\ast b[j]$
得证
　　所以，决策单调性是存在的。我们将由决策单调性得出的式子展开，化成斜率式：

a[i]∗b[j]+c[j]+d[i]>=a[i]∗b[k]+c[k]+d[i]，j<k$a[i]\ast b[j]+c[j]+d[i]>=a[i]\ast b[k]+c[k]+d[i]，j<k$

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

　　记斜率
slope(i,j)=c[k]−c[j]b[k]−b[j]$slope(i,j)=c[k]-c[j]b[k]-b[j]$

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

−a[i]>=slope(q[l],q[l+1])$-a[i]>=slope(q[l],q[l+1])$。因为q[l]$q[l]$在q[l+1]$q[l+1]$之前加入，那么显然这个式子就表示q[l]$q[l]$决策不如q[l+1]$q[l+1]$优，我们可以将队首pop掉。
slope(q[r−1],q[r])>slope(q[r],i)$slope(q[r-1],q[r])>slope(q[r],i)$。假设我们在后面存在一个a[t]$a[t]$使得−a[t]>=slope(q[r−1],q[r])$-a[t]>=slope(q[r-1],q[r])$那么等到pop了q[r−1]$q[r-1]$之后，−a[t]$-a[t]$一定也会>=slope(q[r],i)$slope(q[r],i)$，q[r]$q[r]$也会被pop。所以说q[r]$q[r]$实际上是无用的，我们可以直接将它pop掉。
　　问题就这样优化到了O(n)$O(n)$。

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

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

形

　　dp方程：
f[i]=Min(a[i]∗b[j]+c[j]+d[i])$f[i]=Min(a[i]\ast b[j]+c[j]+d[i])$，b[j]单增

　　我们这里沿用上面“数”的条件：a单减，b单增。

　　移项：
−a[i]∗b[j]+f[i]=c[j]+d[i]$-a[i]\ast b[j]+f[i]=c[j]+d[i]$

　　是不是很像直线的斜截式：−a[i]$-a[i]$为直线的斜率；直线过点：(b[j],c[j]+d[i])$(b[j],c[j]+d[i])$；f[i]$f[i]$即为直线在Y轴上的截距。

　　
　　可以看出，因为f[i]$f[i]$要尽可能小，所以我们把之前小于i$i$的j$j$画在平面直角坐标系上，一如线性规划，把这条斜线自下往上平移时遇到的第一个点，即能使目前状态有最小值的点。于是我们需要维护一个下凸壳，把那些肯定不会贡献的点删掉。

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

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

斜率−a[i]$-a[i]$单增（因为a$a$单减）。−a[i]>slope(q[l],q[l+1])$-a[i]>slope(q[l],q[l+1])$。
斜率不单调。无法pop队首，二分或者三分查找队列中的最优解。二分做法：假设你要在上凸包上二分找斜率为k的切线。取中间的mid$mid$号点，如果mid+1$mid+1$存在且与mid$mid$点的斜率小于k$k$，则l=mid+1$l=mid+1$；如果mid−1$mid-1$存在且与mid$mid$点的斜率大于k$k$，则r=mid−1$r=mid-1$；如果上面两条都不满足，则mid$mid$就是切点。
　　不错，你一定已经发现第一种情况所对应的维护方式不是跟之前所说“数”的单调队列维护方式一模一样吗，没错，其实这只是两种不同的解题方式所得出来的同样的结果。

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

　　之前说的决策单调性是斜率优化的基础这句话其实并不严谨，像这种从图形角度来求解的斜率优化就并没有用到决策单调性。想一想如果能证明决策单调性，那么一定就是对a和b的单调性有要求的，否则的话就是什么斜率不单调啦，在凸包上二分啦什么的。

　　这就是斜率优化啦。

小科普

　　回顾之前斜率优化的运用，它必须要有一个前提条件：b$b$（横坐标）单增。而如果b[j]$b[j]$不单调怎么办呢？还能不能用斜率优化呢？

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

总结

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

参考资料：

http://blog.sina.com.cn/s/blog_7a1746820100xztv.html

http://tieba.baidu.com/p/3671167462

http://blog.csdn.net/u010336344/article/details/52693858

This passage is made by MashiroSky.