跳转至

单调队列优化DP

引入

首先我们对于一个 "DP方程式" ：

\[ f_i = \min_{l_i\le j \le r_i}\{f_j+a_j\} + b_i ~~~~ (r_i < i) \]

此时我们考虑如和求解一个 \(i\) 的决策点 \(p_i\) 。 由于 \(b_i\) 是固定的，所以我们只需要满足 \(\{f_j+a_j\}\) 最小。此时我们发现这一部分只和 \(j\) 有关，而和当前所选择的 \(j\) 无关。所以我们就有一个十分简单的思路：

线段树优化DP

我们建立一颗线段树，其下标 \(i\) 位置存储的是 \(\{f_i+a_i\}\) 。

然后对于一次迭代 \([l_i,r_i]\) ，就查询这个区间内的最小值。

这个方案时间复杂度 \(\mathcal O(N\log N)\) ，几乎大部分数据都可以通过。但是这个算法还是有一下缺点：

  1. 代码相对较长

  2. 时间复杂度多了一个 \(\mathcal O(\log N)\) ，如果正好题目就卡你可能过不去。

所以对于这里类方程的一种特殊情况，我们可以通过单调栈优化。

正题

对于 \(l_i, r_i\) 都单调递增的情况，我们可以考虑进行单调队列优化。

具体来说就是对于每一次迭代：

  1. 把 \(j < l_i\) 的丢出去
  2. 把 \(j > r_i\) 的放进去

此时我们可以得到一个十分简单的代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
int l, r, q[N]; // 当前单调队列
int R; // 当前处理的右边界
void solve() {
    // f[i]=min(f[i], f[j]+a[j])+b[i]
    f[0]=0, q[l=r=1]=0;
    for(int i=1; i<=n; i++) {
        while(l<=r && q[l]<l[i]) l++;
        while(R<r[i]) {
            ++R;
            while(l<=r && f[R]+a[R] < f[q[r]]+a[q[r]])
                r--;
            q[l]=R;
        }
        int j=q[++r];
        f[i]=f[j]+a[j]+b[i];
    }
}

总结

实际上就是所有转移区间满足单调性的都可以使用单调队列维护。