跳转至

单调队列优化 DP

单调队列可以在均摊 \(O(1)\) 的时间复杂度内求出滑窗最值。因此，单调队列可以优化这几种 DP 转移：

  • 当前 DP 值由滑窗中的 DP 最值转移而来；
  • 可能的 DP 决策点可由单调队列维护；

推广滑窗最值

推广滑窗最值的定义，单调队列也可以维护：

有一个长为 \(n\) 的序列，第 \(i\) 个位置对应一个点 \((x_i,y_i)\)，保证 \(x_i\) 单调递增。单调队列可以求出：

\[ \max_{j<i,\ x_j\ge x_0}\{y_j\}\\ \max_{j<i,\ y_j\ge y_0}\{x_j\} \]

你需要保证 \(x_0\) 随着 \(i\) 单调递增（即约束越来越严格），\(y_0\) 随着 \(i\) 单调递减（即约束越来越宽松）。

与其对偶的两类问题可以用单调栈维护。

对于两类问题，我们都维护一个 \(y_i\) 对 \(x_i\) 严格递减的单调队列。对于第一类问题，发现 \(x_{head}<x_0\) 时弹出；对于第二类问题，如果弹出队首后仍然有 \(y_{head}\ge y_0\)，则弹出。

直接维护 DP 值

这属于单调队列比较基本的应用。

例题

P2627 [USACO11OPEN] Mowing the Lawn G

P3572 [POI 2014] PTA-Little Bird

P2569 [SCOI2010] 股票交易

P2254 [NOI2005] 瑰丽华尔兹

维护决策点

高效进阶 J5 出题方案

题意

给你一个长度为 \(n\) 的序列 \(a\)。你需要将它划分为若干段，满足每一段的总和不超过常数 \(m\)。要求最小化每一段当然最大值之和。

P5665 [CSP-S2019] 划分

题意

给你一个长度为 \(n\) 的序列 \(a\)。你需要将它划分为若干段，满足每一段的总和 \(\sum_{i=l}^{r} a_i\) 单调不降。最小化

\[ \left(\sum_{j=l_1}^{r_1}{a_j}\right)^2+ \left(\sum_{j=l_2}^{r_2}{a_j}\right)^2+\cdots+ \left(\sum_{j=l_k}^{r_k}{a_j}\right)^2 \]

如果没有段和单调不降的限制，则直接斜率优化即可。

我们有贪心结论：dp 时总是选择最靠后的合法的决策点，即尽可能缩小最后一段的段长。

考虑调整法证明。如图，\(s_1\le s_2\)。对于最后一段 \(s_2\) 的一个前缀 \(x\)，先将它分离出来；如果将它加入 \(s_2\)，则会产生 \(2xs_2\) 的代价；如果能将其加入 \(s_1\)，则会产生不超过 \(2xs_1\) 的代价；当且仅当加入后 \(s_1\) 的左端点右移，代价会小于 \(2xs_1\)，此时一定更优。

记当前 dp 转移点为 \(p\)。将 \(p\) 向右合法的移动，代价就一定会减少，并且倒数第 \(2\) 段 \(s_1\) 变长不会超过 \(x\)。同时最后一段更短对后面的转移也有利。因此一定更优。

也即：若找到两个合法的转移点 \(p_1\) 和 \(p_2\)，且满足 \(p_1<p_2\)，则将 \(p_1\) 调整为 \(p_2\) 一定更优。

示意图

我们记 \(g_i\) 为前缀 \(i\) 的最优决策点。写出转移式：

\[ \begin{align*} f_i=&\max_{j< i\text{ and }s_j-g_j\le s_i-s_j}\Big\{f_j+(s_i-s_j)^2\Big\}\\ g_i=&\max_{j< i\text{ and }s_j-g_j\le s_i-s_j}\{j\} \end{align*} \]

重点关注转移的条件，将其变形：

\[ s_i\ge 2s_j-g_j \]

这正是单调队列优化的第二类问题（限制愈加宽松，求单增维度的最值）。我们维护一个 \(2s_i-g_i\) 对 \(i\) 单调递增的队列，如果弹出队首后的新队首仍然满足条件，则弹出队首，以保持队首总是满足 \(2s_i-g_i\le s_0\) 中 \(i\) 最大的一个。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<iostream>
#define ll long long
using namespace std;
const int N = 4e7 + 10;
const int M = 1e5 + 10;

void gen(int &n, int *a) {
    int tp;
    cin >> n >> tp;
    if(tp == 0) {
        for(int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        return;
    }
    int x, y, z, m, b1, b2;
    cin >> x >> y >> z >> b1 >> b2 >> m;
    int p = 0, l, r;
    for(int i = 1; i <= m; i++) {
        int tmp = p;
        cin >> p >> l >> r;
        for(int j = tmp + 1; j <= p; j++) {
            int b;
            if(j == 1) b = b1;
            else if(j == 2) b = b2;
            else {
                b = ((ll)y * b1 + (ll)x * b2 + z) % (1 << 30);
                b1 = b2;
                b2 = b;
            }
            a[j] = b % (r - l + 1) + l;
        }
    }
}

#define int __int128

signed n;
signed a[N], g[N];
ll s[N];

signed que[N], head, tail;

bool flag[N];

signed main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    gen(n, a);

    for(int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + a[i];
    }

    head = 1, tail = 0;
    que[++tail] = 0;

    for(int i = 1; i <= n; i++) {
        while(head < tail && (2 * s[que[head + 1]] - s[g[que[head + 1]]]) <= s[i]) ++head;
        g[i] = que[head];
        while(head <= tail && (2 * s[que[tail]] - s[g[que[tail]]]) >= (2 * s[i] - s[g[i]])) --tail;
        que[++tail] = i;
    }

    for(int i = n; i; i = g[i]) {
        flag[i] = 1;
    }

    int ans = 0;
    for(int i = 1; i <= n; i++) {
        if(flag[i]) ans = ans + ((int)s[i] - s[g[i]]) * (s[i] - s[g[i]]);
    }

    char buf[60], cnt = 0;
    while(ans) {
        buf[++cnt] = ans % 10 + 48;
        ans /= 10;
    }

    for(int i = cnt; i >= 1; i--) {
        cout << buf[i];
    }
    cout << endl;

    return 0;
}