跳转至

单调队列优化 DP

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

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

直接维护 DP 值

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

P2627 [USACO11OPEN] Mowing the Lawn G

P3572 [POI 2014] PTA-Little Bird

P2569 [SCOI2010] 股票交易

P2254 [NOI2005] 瑰丽华尔兹

推广滑窗最值

单调队列能维护的不仅仅是滑窗最值。通过一些归纳，我们可以得到这类问题的普遍性规律：

  • 有一个长为 \(n\) 的序列，每个位置对应一个具有二元信息的元素 \((a_i,b_i)\)；
  • \(a_i\) 和 \(b_i\) 的其中之一具有单调性；
  • 当两个元素 \(j_1,j_2\) 满足某种偏序关系时，其中一个元素一定不能在之后的转移中产生贡献；

大部分这类问题都可以使用单调队列（单调栈）维护。由于其偏序更优的性质，我们可以使单调队列中的元素同时具有两个维度的单调性。这样，一个二元问题就被转化为了一个一元问题。

维护决策点

Y56A 出题方案

题意

给你一个长度为 \(n\) 的序列 \(a_{1\sim n}\)，你需要将它划分为若干段，使得每一段的 \(sum\) 不超过常数 \(m\)。要求最小化每一段的最大值之和。

\(n\le 3\times 10^5\)

考虑 dp，设 \(f_i\) 表示前缀 \(i\) 的答案。显然，转移区间是一个滑窗形式，并且滑窗的左端点可以通过双指针 \(O(1)\) 得到。

\[ f_i=\min_{p_i\le j< i}\{f_{j}+\max[j+1,i]\} \]

考虑如何处理 \(\max\) 的这一项。注意到这形如一个“动态”的后缀最大值，可以使用单调队列维护极值点。然而，这里的转移点没有偏序性质，不能直接使用单调队列。

在单调队列维护动态后缀最大值的过程中，我们注意到队列中的每一个极值点实际都有一段“管辖区间”；在这个管辖区间内，只能靠 \(f_j\) 分出胜负。同时我们注意到，\(f_i\) 是单调不降的，因此一段区间内最靠左的位置一定是 \(f_i\) 的最小值，也是区间中唯一可能产生贡献的决策点。

然而，随着 \(i\) 的增大，后缀 \(mx\) 可能会增大、变劣；因此我们不能直接使用单调队列维护 \(f_l\)。注意到数据范围并没有要求线性，因此我们可以使用一个 multiset 或者可删堆维护 \(f_l+a_r\) 的最小值。

代码 
 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
#include<iostream>
#include<set>
#define int long long
using namespace std;
const int N = 3E5 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;

int n, m;
int a[N], f[N], s[N];

struct myPair {
    int l, r, mx, v;
    inline bool operator<(const myPair &b) const {
        return v < b.v;
    }
};

multiset<myPair> st;

inline void insert(const myPair &x) { st.insert(x); }
inline void erase(const myPair &x) { st.erase(st.find(x)); }
inline int query() { return st.begin()->v; }

myPair que[N];
int hd, tl;

signed main() {

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

    hd = 1, tl = 0;
    for(int i = 1, j = 1; i <= n; i++) {
        while(j <= i && s[i] - s[j - 1] > m) ++j;
        while(hd <= tl && que[hd].r < j) {
            erase(que[hd]);
            ++hd;
        }
        if(hd <= tl && que[hd].l < j) {
            erase(que[hd]);
            que[hd].l = j;
            que[hd].v = que[hd].mx + f[j];
            insert(que[hd]);
        }
        while(hd <= tl && que[tl].mx <= a[i]) {
            erase(que[tl]);
            --tl;
        }
        if(hd <= tl) que[tl + 1] = {que[tl].r + 1, i, a[i], f[que[tl].r + 1] + a[i]}, ++tl;
        else que[++tl] = {j, i, a[i], f[j] + a[i]};
        insert(que[tl]);
        f[i + 1] = query();
    }

    cout << f[n + 1] << '\n';

    return 0;
}

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 \]

\(n\le 4\times 10^7\)，\(a\) 使用数据生成器输入。

如果没有段和单调不降的限制，则直接钦定每段长度为 \(1\) 一定不劣。

我们有贪心结论：对于一段前缀的子问题，我们在合法的前提下尽可能缩短最后一段的长度，一定不劣。

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

对于前缀 \(i\) 的子问题，将转移点 \(p\) 向右移动，子问题的总代价一定减少；并且由于最后一段长度变短，对后面的转移也有利。因此一定不劣。

示意图

考虑转移。记 \(g_i\) 为前缀 \(i\) 的最优决策点。我们有：

\[ g_i=\max_{sum(g_j,j)\le sum(j,i)}\{j\} \]

其中 \(sum(l,r)\) 表示左开右闭区间 \((l,r]\) 的区间和。这种形式不易优化，我们将 \(sum\) 展开成前缀和的形式：

\[ \begin{align*} s[j]-s\big[g[j]\big]&\le s[i]-s[j]\\ 2s[j]-s\big[g[j]\big]&\le s[i] \end{align*} \]

这是一种两个维度的最优化问题，并且其中一个维度具有单调性，考虑单调数据结构。记 \(h[i]=2s[i]-s\big[g[i]\big]\)。考虑两个决策点 \(j_1<j_2\)，若满足 \(h[j_1]\ge h[j_2]\)，我们可以直接弹出 \(j_1\)。这样，我们使用一个单调队列维护决策点 \(j\)，满足其中的 \(j\) 单调递增，\(h_j\) 也单调递增。任意时刻合法的 \(j\) 总是单调队列中的一个前缀，并且由于 \(s[i]\) 单调递增，该前缀会不断向右扩展。容易发现，只保留前缀中最靠右的一个合法决策点即可，并且该决策点一定是最优决策点 \(g_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;
}