M_sea

「总结」斜率优化
其实这东西早该写了,因为某些原因一直咕到现在概念斜率优化是一种对dp的优化,通过单调性优化掉一个$n$的复杂度。比...
扫描右侧二维码阅读全文
22
2019/01

「总结」斜率优化

其实这东西早该写了,因为某些原因一直咕到现在

概念

斜率优化是一种对dp的优化,通过单调性优化掉一个$n$的复杂度。

比如,本来是$O(n^2)$的dp,可以优化到$O(n)$。

推导

假设有一个状态转移方程是这样的(当然$\max$也是可以的):

$f[i]=\min\left\{f[j]+w(i,j)\right\}$

这个$w(i,j)$是一个只和$i$和$j$有关的函数。

然后,假设从$j$转移过来优于从$k$转移过来。

然后就有:

$f[j]+w(i,j)<f[k]+w(i,k)$

再进一步,设$w(i,j)=g(i)h(j)$,其中$g(i)$是只和$i$有关的函数,$h(j)$是只和$j$有关的函数。

然后可以得到:

$f[j]+g(i)h(j)<f[k]+g(i)h(k)$

移项:

$g(i)\big(h(j)-h(k)\big)<f[k]-f[j]$

除过去(当然可能会要变号):

$g(i)<\frac{f[k]-f[j]}{h(j)-h(k)}$

右边这个式子可以看做斜率,右边这个东西可以看做直线的两点式。

然后根据符号来判断是维护一个上凸壳还是下凸壳。

至于具体怎么维护凸壳,还要根据函数的单调性来。常用的有单调队列、平衡树、或者 $\mathrm{CDQ}$ 分治。

习题

具体做题的时候,最好先写一个暴力dp,再套式子来优化。

HNOI2008 玩具装箱TOY&题解

APIO2010 特别行动队&题解

NOI2007 货币兑换&题解

最后修改:2019 年 04 月 05 日 01 : 27 PM

2 条评论

  1. smy

    是斜率满足单调性就可以用单调队列,不然可能要在凸壳上二分

    1. M_sea
      @smy

      已修改

发表评论