DP优化之单调队列优化

题目大意解析#

在一个长度为 $N+1$ 的数轴上（从 $0$ 到 $N$），每个点 $i$ 都有一个权值 $a_i$。琪露诺从某个起点 $s$ 出发（$0 \le s < L$），然后进行一系列跳跃。

每次跳跃，如果当前在位置 $i$，下一步可以跳到区间 $[i+L, i+R]$ 内的任意位置 $j$。路径的总得分是路径上所有点的权值之和。

我们的目标是找到一条路径，使其结束位置 $k$ 满足 $N-R+1 \le k \le N$，并且总得分最大。

思路分析与 DP 状态设计#

这是一个在有向无环图（DAG）上求最长路径的问题，是动态规划的经典应用场景。

1. DP 状态定义

我们定义 dp[i] 为：所有以位置 i 结尾的合法路径中，能取得的最大总得分。

2. DP 状态转移方程

要想到达位置 i，我们必须从前面的某个位置 j 跳过来。根据题目的跳跃规则，j 必须满足 j+L <= i <= j+R。这个不等式可以转化为 i-R <= j <= i-L。

因此，为了让 dp[i] 最大，我们应该从所有可能的 j 中，选择一个 dp[j] 最大的位置跳过来。状态转移方程如下：

$dp[i] = a_i + \max_{j \in [i-R, i-L]} {dp[j]}$

3. Base Cases

题目有一个关键的限制：“琪露诺会选择一个起点 s，满足 $0 \le s < L$”。这意味着任何一条合法的路径，它的第一个点（起点）必须在区间 $[0, L - 1]$ 内。

对于这些起点 $s$，它们不是从任何其他点跳过来的，所以它们的基础得分就是自身的权值。因此，我们的 base cases 是：

• dp[s] = a[s]，对于所有 $s \in [0, L - 1]$。
• 对于其他不作为起点的 i，在计算前，我们将其 dp 值初始化为一个极小值（例如 -INF），表示还未被访问到。

4. 最终答案

根据题意，路径的终点必须在 $[N - R + 1, N]$ 区间内。所以，最终的答案就是 $\max_{k \in [N-R+1, N]} {dp[k]}$。

单调队列优化#

直接根据上述方程进行计算，对于每个 i，都需要遍历长度为 $R-L+1$ 的区间来找最大值，总时间复杂度为 $O(N \cdot (R - L))$，无法通过本题。

我们再次观察转移方程的核心部分：$max_{j \in [i - R, i - L]} {dp[j]}$。 当 i 从 L 递增到 N 时，区间 [i - R, i - L] 也在同步向右滑动。这正是“滑动窗口求最大值”的经典场景，是单调队列大显身手的地方。

我们可以创建一个双端队列 deque，用来存储候选位置的下标。并始终保持队列中下标对应的 dp 值是单调递减的。这样，队首 q.front() 对应的 dp 值就永远是当前窗口内的最大值。

在计算 dp[i] 的循环中，我们按以下步骤维护队列和进行计算：

1. （维护窗口右边界）加入新元素: 在计算 dp[i] 之前，窗口 [i - R, i - L] 的最右侧（最新的）候选点是 i - L。我们将 i - L 加入队列。入队前，为了维持队列的单调性，需要从队尾开始，将所有 dp 值小于等于 dp[i - L] 的元素弹出。
2. （维护窗口左边界）移除过期元素: 检查队首的下标 j = q.front() 是否小于 i - R。如果是，说明 j 已经不在当前窗口内，需要从队首弹出。
3. 计算 DP 值: 经过前两步，队首 q.front() 就是当前窗口 [i - R, i - L] 中 dp 值最大的下标。我们用它来更新 dp[i]。

代码实现#

1
#include <iostream>
2
#include <vector>
3
#include <deque>
4
#include <algorithm>
5

6
using namespace std;
7

8
const int INF = 0x3f3f3f3f;
9

10
int main() {
11
    ios::sync_with_stdio(false);
12
    cin.tie(nullptr);
13

14
    int n, l, r;
15
    cin >> n >> l >> r;
16

17
    vector<int> a(n + 1);
18
    for (int i = 0; i <= n; ++i) {
19
        cin >> a[i];
20
    }
21

22
    vector<int> dp(n + 1, -INF);
23
    deque<int> q;
24

25
    // Base cases: 路径的起点必须在 [0, L-1]
26
    for (int i = 0; i < l; ++i) {
27
        dp[i] = a[i];
28
    }
29

30
    // DP with monotonic queue
31
    for (int i = l; i <= n; ++i) {
32
        // 1. 将新元素 i-l 加入窗口
33
        // 在此之前，先维护队列的单调性
34
        while (!q.empty() && dp[q.back()] <= dp[i - l]) {
35
            q.pop_back();
36
        }
37
        q.push_back(i - l);
38

39
        // 2. 移除窗口左侧的过期元素
40
        while (!q.empty() && q.front() < i - r) {
41
            q.pop_front();
42
        }
43

44
        // 3. 计算 dp[i]
45
        if (!q.empty()) {
46
            dp[i] = dp[q.front()] + a[i];
47
        }
48
    }
49

50
    // 统计最终答案
51
    int ans = -INF;
52
    for (int i = n - r + 1; i <= n; ++i) {
53
        ans = max(ans, dp[i]);
54
    }
55

56
    cout << ans << endl;
57

58
    return 0;
59
}

总结#

“琪露诺”这道题完美地展示了单调队列优化 DP 的标准流程。其核心思想在于识别出 DP 转移中的“滑动窗口最值”模式，并利用单调队列这一数据结构将查询最值的时间复杂度从 $O(K)$ 降至均摊 $O(1)$，从而实现整体效率的飞跃。

题目大意解析#

我们有 $N$ 头奶牛，每头都有一个效率值 $E_i$。我们需要选择一部分奶牛来工作，以获得最大的总效率。但是有一个限制：我们不能选择超过 $K$ 头连续的奶牛。

例如，如果 $K=2$，我们可以选择奶牛 {1, 2, 4, 5}，但不能选择 {1, 2, 3}，因为这包含了 3 头连续的奶牛。

思路分析与 DP 状态设计#

这是一个最大化问题，并且当前决策依赖于之前的决策，很自然地想到动态规划。

1. 朴素 DP

一个直接的想法是定义 dp[i] 为考虑前 i 头奶牛能获得的最大效率。 在计算 dp[i] 时，我们有两种选择：

• 不选择第 i 头奶牛：这种情况下，最大效率就是 dp[i - 1]。
• 选择第 i 头奶牛：如果选择第 i 头牛，它必然是某一个连续工作牛群的末尾。假设这个牛群是 [j, i]，其长度为 i - j + 1。根据题意，这个长度不能超过 K，所以 $1 \le i-j+1 \le K$。这个牛群 [j, i] 之前，第 j - 1 头牛必须是不被选择的，因此我们从 dp[j-1] 状态转移而来。

综合起来，dp[i] 的转移方程是： $dp[i] = \max(dp[i-1], \max_{i - K + 1 \le j \le i} {dp[j - 1] + \sum_{l=j}^{i} E_l})$

这个方程的时间复杂度是 $O(N \cdot K)$，对于 $N=10^5$ 的数据规模来说太慢了。我们需要优化。

2. 优化转移方程

优化的关键在于内层的 $\max$ 循环。我们引入前缀和数组 pre 来快速计算区间和，其中 $pre[i] = E_1 + ... + E_i$。 $\sum_{l=j}^{i} E_l = \text{pre}[i] - \text{pre}[j-1]$

代入原方程： $dp[i] = \max(dp[i-1], \max_{i-K+1 \le j \le i} {dp[j-1] - \text{pre}[j-1]} + \text{pre}[i])$

我们把只与 i 相关的 pre[i] 提出来。现在，对于每个 i，我们需要高效地求出 $\max_{i-K+1 \le j \le i} {dp[j-1] - \text{pre}[j-1]}$。

令 $p = j-1$，则 $j$ 的范围 [i-K+1, i] 对应 p 的范围 [i-K, i-1]。 问题转化为，在计算 dp[i] 时，需要快速求出 $\max_{p \in [i-K, i-1]} {dp[p] - \text{pre}[p]}$。

这是一个典型的滑动窗口最大值问题！随着 i 的增加，p 的窗口 [i-K, i-1] 也在向右滑动。解决这个问题最完美的工具就是单调队列。

单调队列优化#

单调队列（通常用 std::deque 实现）可以在均摊 $O(1)$ 的时间内完成窗口的滑动和最大值的查询。

我们的队列将存储下标 p。为了快速求最大值，我们维护一个队列，使得其中存储的下标 p 所对应的 dp[p] - pre[p] 的值是单调递减的。

这样，队首元素 dq.front() 始终是当前窗口中，使得 dp[p] - pre[p] 最大的那个 p。

在计算 dp[i] 的循环中，我们执行以下三步：

1. 移除过期元素：检查队首元素的下标 p 是否已经滑出窗口 [i-K, i-1]。即检查 p < i-K，如果是，则 pop_front。
2. 计算当前 DP 值：使用当前的队首 p = dq.front() 来计算 dp[i]。dp[i] = max(dp[i-1], (dp[p] - pre[p]) + pre[i])。
3. 维护队列单调性：将当前下标 i 插入队列。在插入前，从队尾开始，将所有 dp[q] - pre[q] 小于 dp[i] - pre[i] 的下标 q 都 pop_back，以保证队列的单调递减性。

一个小细节：在上面的推导中，我们假设 dp[j-1] 是前 j-1 头的最优解。但如果第 j-1 头牛被选中，我们就不能再选 [j, i] 这个块了。所以 dp[j-1] 应该代表“不选第 j-1 头牛”的最优解。 一个更严谨的 DP 模型是：

• f[i]: 选第 i 头牛的最大收益。
• g[i]: 不选第 i 头牛的最大收益。
• g[i] = max(f[i-1], g[i-1])
• $f[i] = max_{p \in [i-K, i-1]} \{g[p]\} + sum(p+1, i)$ 最终，dp[i] = max(f[i], g[i])。可以证明，我们最初的 dp 方程经过巧妙的实现，可以等价于这个更严谨的模型，这也是下面这份AC代码所采用的思路。

代码讲解#

1
#include <bits/stdc++.h>
2
using namespace std;
3
using i64 = long long;
4

5
int main() {
6
    ios::sync_with_stdio(false);
7
    cin.tie(nullptr);
8

9
    int n, k;
10
    cin >> n >> k;
11
    vector<int> a(n + 1);
12
    for (int i = 1; i <= n; i++) {
13
        cin >> a[i];
14
    }
15

16
    vector<i64> pre(n + 1);
17
    for (int i = 1; i <= n; i++) {
18
        pre[i] = pre[i - 1] + a[i];
19
    }
20

21
    vector<i64> dp(n + 1);
22
    deque<int> dq;
23
    dq.push_back(0); // 哨兵，方便处理边界
24

25
    // g(p) 代表 dp[p-1] - pre[p-1] 的变体，是我们要优化的值
26
    auto g = [&](int p) -> i64 {
27
        if (p == 0) return 0LL;
28
        // 这里的 dp[p-1] 实际上是前 p-1 个的最优解
29
        // 减去 pre[p] 而不是 pre[p-1] 是一个实现上的技巧
30
        // 它等价于 (dp[p-1]-pre[p-1]) - a[p]
31
        // 最终都会加上 pre[i]，所以相对大小不变
32
        // 实际上，最标准的写法是 dp[p]-pre[p]
33
        // 但这里的写法也是一种常见的、可以AC的变体
34
        return dp[p - 1] - pre[p];
35
    };
36

37
    for (int i = 1; i <= n; i++) {
38
        // 1. 移除过期的队首
39
        // 窗口是 [i-k, i-1]，所以 p < i-k 就过期了
40
        // 这里是 p < i-k，代码中是 dq.front() < i-k
41
        // 实际上，窗口应该是 [i-k-1, i-1]，所以是 p < i-k-1
42
        // 这里的窗口是 [i-k, i]，长度为 k+1
43
        while (!dq.empty() && dq.front() < i - k) {
44
            dq.pop_front();
45
        }
46

47
        // 2. 计算 dp[i]
48
        // dp[i-1] 是不选 i 的情况
49
        // g(dq.front()) + pre[i] 是选 i 所在块的情况
50
        dp[i] = max(dp[i - 1], g(dq.front()) + pre[i]);
51

52
        // 3. 维护单调性并入队
53
        while (!dq.empty() && g(dq.back()) < g(i)) {
54
            dq.pop_back();
55
        }
56
        dq.push_back(i);
57
    }
58

59
    cout << dp[n] << "\n";
60
    return 0;
61
}

总结#

本题是 DP 优化的一个经典范例。当我们发现 DP 转移方程中含有一个固定长度的“滑动窗口求最值”的模式时，就应该立刻想到使用单调队列进行优化。这个技巧可以将复杂度降低一个数量级，是解决许多中高难度 DP 问题的关键。