动态规划的优化方法

单调队列优化

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

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

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

斜率优化

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

考虑两个决策 $j$ 和 $k$ ($j < k$),如果 $k$ 比 $j$ 优,则

$$s[i] \times x[j] + y[j] \leq s[i] \times x[k] + y[k]$$

化简得:

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

这里假设 $x_k > x_j$ (不然需要变号)

不等式左边可以理解为一个斜率,我们把它设为$slope(j,k)$

可以发现,如果 $slope(q[r-1],q[r]) \geq slope(q[r],i)$,那么当前者成立时,后者必定成立。 即 $q[r]$ 决策优于 $q[r-1]$ 决策时, $i$ 必然优于 $q[r]$,所以 $q[r]$ 就没有存在的必要了。因此我们可以用一个斜率单调递增的队列来维护所有决策点。

每次决策的时候,只要在队列中找到满足下面条件的元素进行转移即可:

$$\begin{cases}
slope(q[p-1],q[p]) \leq s[i]\\
slope(q[p],q[p+1]) > s[i]
\end{cases}$$

因为队列是按斜率单调递增的,因此我们可以去二分这个决策点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int l = 1, r = 1;
q[l] = 0; // 0 这个决策点要赋初值
for (int i = 1; i <= n; i++) {
int p, L = l, R = r;
while (L <= R) {
int mid = L + R >> 1;
if (slope(q[mid - 1], q[mid]) <= s[i]) {
p = mid;
L = mid + 1;
} else
R = mid - 1;
}
// q[p] 为决策点
while (l < r && slope(q[r - 1], q[r]) >= slope(q[r], i)) r--;
q[r] = i;
}
// slope的比较一般写成交叉相乘的形式

特别的对于 $s[i]$ 是单调不降的情况:

因为当 $slope(q[l], q[l+1]) \leq s[i]$ 时,必然有 $slope(q[l], q[l+1]) < s[i+1]$。因此 $q[l+1]$ 这个决策将会永远优于 $q[l]$ 这个决策。因此 $q[l]$ 就没有存在的必要了。

因此我们可以将转移的复杂度从上面的 $O(\log(n))$ 优化为均摊 $O(1)$。

每次决策的时候,如果对于队头元素有 $slope(q[l], q[l+1]) \leq s[i]$,这说明 $q[l+1]$ 比 $q[l]$ 优,我们就可以把 $q[l]$ 移出队列。(如果 $s[i]$ 不是单调的,就不可以移出队列!)

每次向队列加入新的元素时,如果有 $slope(q[r-1],q[r]) \geq slope(q[r], i)$,那么说明若 $q[r]$ 比 $q[r-1]$ 优,那么 $i$ 一定比 $q[r]$ 优,所以去 $q[r]$ 就没有存在的必要,因此可以把 $q[r]$ 移除队列。

1
2
3
4
5
6
7
8
9
int l = 1, r = 1;
q[l] = 0; // 0 这个决策点要赋初值
for (int i = 1; i <= n; i++) {
while (l < r && slope(q[l], q[l + 1]) <= s[i]) l++;
// q[l] 为决策点
while (l < r && slope(q[r - 1], q[r]) >= slope(q[r], i)) r--;
q[r] = i;
}
// slope的比较一般写成交叉相乘的形式