斜率优化DP
单状态的斜率优化
写出状态转移方程,形如:
$$ f[j]=\max_{i=1}^{j-1} { F_1(j)+F_2(i)+F_3(i,j)} $$
由于$F_3$涉及i和j,若枚举两个变量会超时。
化简方程,得到
$$ f[j]=\max_{i=1}^{j-1} {F_2(i)+F_4(j)*F_5(i) } + const(j) $$
这里涉及的每个函数都能事先算出。于是求最大值转化为线性规划:将$f[j]$看作b,$F_2(i)$看作y,$-F_4(j)$看作k,$F_5(i)$看作x,则形式可转化为$b=y-kx$,求b的最大值。维护可能的点队列,则这是一条上凸线,用二分找到最相近斜率的线段的对应点即可。
某些题目的$F_4(j)$具有单调性,即目标直线的斜率有单调性,则可用朴素单调队列代替二分。
也可以将max改成min,这时求最小的b,维护下凸线即可。
双状态的斜率优化
拓展单状态下的方程,形如:
$$ f(j,k]=\max_{i=1}^{j} { F_1(j,k]+F_2(i,j]+F_3(i,j,k)} $$
同样化简方程,得到
$$ f(j,k]=\max_{i=1}^{j} { F_2(i,j]+F_4(i)*F_5(j,k]} + const(j,k]$$
类似地令$F_4(i)$为横坐标x,待求的$f(j,k]$看作截距b,$F_2(i,j]$看作纵坐标y构建线性规划。之后的步骤同上。
斜率优化的目的是减少枚举前驱状态的时间,用O(1)或O(log n)完成状态转移。这将要求在完成状态计算后,将新获得的点加入凸线中。加点后,视情况选择是否维护凸性。
对于双状态的题目,不同的j对应不同的凸线(这是因为$F_2(i,j]$会随j变化,即点的坐标会变化)。应当判断对于同一个j、不同的k,能否从同一条凸线得到答案。
如果加点操作的横坐标具有非单调性,可能需要数据结构支持二分查找、中间加点、中间删点的操作。如果不需要即时维护,可以用排序完成维护。