动态规划的优化方法

单调队列优化

对于状态是一维,转移也是一维的dp, 可以用单调队列进行优化.

$dp[i] = min( A(i) + B(k) ) , k \in [l,i-1]$

那么可以用一个单调队列来维护$B(k)$, 这样可以把复杂度降到O(n)

斜率优化

问题: 设 $f(i) = min( y[k] - s[i] \times x[k]), k \in [1,i-1]$, 现在要求出所有$f(i), i \in [1,n]$

考虑两个决策j和k,如果j比k优,则

$$y[j] - s[i] \times x[j] < y[k] - s[i] \times x[k]$$

化简得:

$$\frac{y_j - y_k}{x_j - x_k} < s_i$$

不等式左边是个斜率,我们把它设为$slope(j,k)$

我们可以维护一个单调递增的队列,为什么呢?

因为如果$slope(q[i-1],q[i]) > slope(q[i],q[i+1])$,那么当前者成立时,后者必定成立。 即$q[i]$决策优于$q[i-1]$决策时,$q[i+1]$必然优于$q[i]$,因此$q[i]$就没有存在的必要了。 所以我们要维护递增的队列。

那么每次的决策点i,都要满足
$$\begin{cases}
slope(q[i-1],q[i]) < s[i]\\
slope(q[i],q[i+1]) >= s[i]
\end{cases}$$

一般情况去二分这个i即可。

如果$s[i]$是单调不降的,那么对于决策j和k(j < k)来说,如果决策k优于决策j,那么对于$i \in [k+1,n]$,都存在决策k优于决策j, 因此决策j就可以舍弃了。 这样的话我们可以用单调队列进行优化,可以少个$log$

如果还是有点模糊的话,请去做一下bzoj1010,然后我的这篇题解用来上述一抹一样的方法进行分析。

Thank you for your support!