如果DP转移方程满足dp[i] = min { a[i]x[j] + b[i]y[j] | j < i }的形式, 则可以进行斜率优化.
Link: - 1D/1D动态规划优化初步
斜率优化和平面上的线性规划密切相关.
把决策看成平面上的一个点 (x[j], y[j]), 那么, 需要找到最小的z, 使得直线 z = ax+by 经过至少一个决策点且z最小.
当 b≠0, 换用斜截式, 则该直线为 y = -a/b x + z/b. 不妨设 ab>0, 想象一条斜率为负的直线从y轴负无穷向正无穷移动, 直至碰到一个决策点. 该点一定在所有决策点的下凸壳上. 所以, 维护决策点形成的下凸壳即可.
决策点的横/纵坐标单调
这里的单调性是关于j的.
如果横坐标不单调而纵坐标单调, 将它们互换即可.
此时, 凸壳可直接用单调栈维护, 做graham-scan式的更新即可.
最优决策点的选取可二分查找.
直线的斜率也单调
当 ab>0 时, 直线的斜率单增才有意义. 如果凸壳不变, 则最优决策点单调右移. 现在往右边加点. 如果当前最优点被保留, 则没啥; 如果被弹掉, 则新点必然优于当前点, 原来劣于当前点的点, 现在并不会变优, 所以也没啥.
因此, 单调栈变成支持头部删除的单调队列, 保持队首为最优点.
决策点的横纵坐标均不单调
用平衡树维护凸壳, 或者CDQ分治.
CDQ分治
先递归计算左边, 然后对左边建凸壳, 更新右边, 最后递归计算右边.
建凸壳需要对点按横坐标排序, 可以在分治的过程中归并排序.
为了O(n)地用左边的凸壳更新右边, 右边的斜率也需要排序, 可以在所有分治之前sort一遍, 然后在每层分离出左边, 右边的斜率 (归并排序的逆过程). 如果斜率本身已有单调性, 则可以省略.