单调队列优化DP

单调队列在 DP 中的基本应用，是对这样一类 DP 状态转移方程进行优化：\(dp[i] = \min \{ dp[j] + a[i] + b[j] \}, L(i) \le j \le R(i)\)。方程中的 \(\min\) 也可以是 \(\max\)，方程的特点是其中关于 \(i\) 的项 \(a[i]\) 和关于 \(j\) 的项 \(b[j]\) 是独立的，而 \(j\) 被限制在窗口 \([L(i),R(i)]\) 内，常见的如给定一个窗口值 \(k\)，即 \(i-k \le j \le i\)。这个 DP 状态转移方程的编程实现，如果简单地对 \(i\) 做外层循环，对 \(j\) 做内层循环，时间复杂度为 \(O(n^2)\)，而如果用单调队列来优化，时间复杂度可以变为 \(O(n)\)。

其本质原因是外层 \(i\) 变化时，不同的 \(i\) 所对应的内层 \(j\) 的窗口有重叠。

如图，\(i=i_1\) 时，对应的 \(j_1\) 的滑动窗口范围是上方的阴影部分；\(i=i_2\) 时，对应的 \(j_2\) 处理的滑动窗口范围是下方的阴影部分；两部分有重叠。当 \(i\) 从 \(i_1\) 增加到 \(i_2\) 时，这些重叠部分被重复计算，如果减少这些重复，就得到了优化。如果把所有重叠的部分都优化掉，那么所有 \(j\) 加起来只从头到尾遍历了一次，此时 \(j\) 的遍历实际上就是 \(i\) 的遍历。

例：P1725 琪露诺

设 \(dp[i]\) 为到达位置 \(i\) 时最大的冰冻指数，则状态转移方程是 \(dp[i] = \min \{ dp[j] \} + a[i]\)，其中 \(i-R \le j \le i-L\)，显然 \(j\) 的选择范围是一个滑动窗口，可以使用单调队列优化。

#include <cstdio>
#include <deque>
using namespace std;
const int N = 2e5 + 5;
const int INF = 2e9;
int a[N], dp[N];
int main()
{
    int n, l, r;
    scanf("%d%d%d", &n, &l, &r);
    for (int i = 0; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) dp[i] = -INF;
    deque<int> q;
    for (int i = l; i <= n; i++) {
        while (!q.empty() && q.front() < i - r) q.pop_front();
        while (!q.empty() && dp[q.back()] < dp[i - l]) q.pop_back();
        q.push_back(i - l);
        if (dp[q.front()] == -INF) continue;
        dp[i] = dp[q.front()] + a[i];
    }
    int ans = -INF;
    for (int i = n - r + 1; i <= n; i++) ans = max(ans, dp[i]);
    printf("%d\n", ans);
    return 0;
}

例：P3957 [NOIP2017 普及组] 跳房子

首先注意到金币花得更多的情况下，得分不可能减少，因此满足二分答案的条件，所以考虑二分花的金币数。注意二分答案的范围是 \([0, \max (d, x_n)]\)，初始弹跳距离 \(d\) 有可能比最后一个格子到起点的距离还要大。

设 \(dp[i]\) 表示调到第 \(i\) 个格子时所能得到的最大分数，注意有的格子可能不可到达，需要令其值为 \(-\infty\)，而 \(dp[0]=0\)，其状态转移方程类似于上一题“琪露诺”，根据当前判定的金币数可以得到升级后的弹跳能力，若单步弹跳范围为 \([L,R]\)，则 \(dp[i] = \min \{ dp[j] \} + a[i]\)，其中 \(i-R \le j \le i-L\)，类似地，用单调队列优化 DP。

#include <cstdio>
#include <deque>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 500005;
const LL INF = 1e12;
int x[N], s[N], n, d, k;
LL dp[N];
bool check(int g) {
    for (int i = 1; i <= n; i++) dp[i] = -INF;
    deque<int> q;
    int minstep = max(d - g, 1);
    int j = 0;
    for (int i = 1; i <= n; i++) {
        while (!q.empty() && x[q.front()] < x[i] - d - g) q.pop_front();
        while (j < i && x[j] <= x[i] - minstep) {
            if (x[j] < x[i] - d - g) {
                j++;
                continue;
            }
            while (!q.empty() && dp[q.back()] < dp[j]) q.pop_back();
            q.push_back(j);
            j++;
        }
        if (q.empty() || dp[q.front()] == -INF) continue;
        dp[i] = dp[q.front()] + s[i];
        if (dp[i] >= k) return true;
    }
    return false;
} 
int main()
{
    scanf("%d%d%d", &n, &d, &k);
    LL pos = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &x[i], &s[i]); 
        if (s[i] > 0) pos += s[i];
    }
    if (pos >= k) {
        int l = 0, r = max(d, x[n]), ans;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (check(mid)) {
                r = mid - 1; ans = mid;
            } else {
                l = mid + 1;
            }
        }
        printf("%d\n", ans);
    } else printf("-1\n");
    return 0;
}

例：P3800 Power收集

给定一个 \(N\) 行 \(M\) 列的棋盘，有 \(K\) 个格子上的值为非零。要求在每一行选择一个格子，并且相邻行选的格子列标号差不超过 \(T\)。最大化选取的格子取值和。
数据范围：\(1 \le N,M,T,K \le 4000\)

分析：记 \(a_{i,j}\) 为格子的权值，设 \(dp_{i,j}\) 表示走到第 \(i\) 行，第 \(j\) 列的最大权值和，显然 \(dp_{i,j} = \max \limits_{1 \le k \le m, |k-j| \le T} \{ dp_{i-1,k}\} + a_{i,j}\)

这个转移实际上就是滑动窗口问题，即区间查询的左端点和右端点都是单调的。每一行 \(dp\) 值计算完成后，可以使用单调队列计算该行 \(dp\) 值中每个窗口的最大值供下一行 \(dp\) 值的计算使用。

#include <cstdio>
#include <deque>
#include <algorithm>
using namespace std; 
const int N = 4005;
int a[N][N], maxv[N][N], dp[N][N];
int main()
{
    int n, m, k, t; scanf("%d%d%d%d", &n, &m, &k, &t);
    while (k--) {
        int x, y, v; scanf("%d%d%d", &x, &y, &v); a[x][y] = v;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) dp[i][j] = maxv[i - 1][j] + a[i][j];
        deque<int> dq;
        int l = 1, r = 1;
        for (int j = 1; j <= m; j++) {
            while (!dq.empty() && dq.front() < j - t) dq.pop_front();
            while (r <= j + t && r <= m) {
                while (!dq.empty() && dp[i][dq.back()] <= dp[i][r]) dq.pop_back();
                dq.push_back(r); r++;
            }
            maxv[i][j] = dp[i][dq.front()];
        }
    }
    int ans = 0;
    for (int i = 1; i <= m; i++) ans = max(ans, dp[n][i]);
    printf("%d\n", ans);
    return 0;
}

例：P2627 [USACO11OPEN] Mowing the Lawn G

问题描述：有一个包括 \(n\) 个正整数的序列，第 \(i\) 个整数为 \(E_i\)，给定一个整数 \(k\)，找这样的子序列，子序列中的数在原序列连续不能超过 \(k\) 个。对子序列求和，问所有子序列中最大的和是多少？\(1 \le n \le 10^5, 0 \le E_i \le 10^9, 1 \le k \le n\)。
例如：\(n=5\)，原序列为 \([7,2,3,4,5]\)，\(k=2\)，选择 \([7,2]\) 和 \([4,5]\)，其最大和为 \(18\)，其中每一段连续长度都不超过 \(k=2\)。

分析：设 \(dp[i]\) 为考虑到前 \(i\) 个整数的答案，状态转移方程为 \(dp[i] = \max \{ dp[j-1] + sum[i] - sum[j] \}\)，其中 \(i-k \le j \le i\)，\(sum[i]\) 为前缀和，即 \(E_1\) 加到 \(E_i\)。也就是说前面有一个位置 \(j\)，该位置上的数不选，因此 \(j\) 之间部分的答案是 \(dp[j-1]\)，而 \(j+1\) 到 \(i\) 这一段全选，这样的考虑对于 \(j\) 之前的部分和之后的部分都没有打破连续长度的限制，注意第 \(i\) 个数自己也可以不选，因此 \(j\) 的考虑范围是 \(i-k\) 到 \(i\)。

在计算 \(dp[i]\) 时 \(i\) 是一个定值，上述方程等价于 \(dp[i] = \max \{ dp[j-1]-sum[j] \} + sum[i]\)，其中 \(i-k \le j \le i\)，因此求 \(dp[i]\) 就是找到做个决策 \(j\) 使得 \(dp[j-1]-sum[j]\) 最大。这个决策范围可视作一个左端点和右端点都单调递增的滑动窗口，因此可以使用单调队列优化。

#include <cstdio>
#include <algorithm>
#include <deque>
using namespace std;
typedef long long LL;
const int N = 100005;
LL dp[N], sum[N];
int e[N];
LL calc(int i) {
    // 技巧：队列中只记录下标，需要比较实际的大小时再代入计算
    return i == 0 ? 0 : dp[i - 1] - sum[i];
}
int main()
{
    int n, k; scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &e[i]); sum[i] = sum[i - 1] + e[i];
    }
    deque<int> dq; dq.push_back(0);
    for (int i = 1; i <= n; i++) {
        // dp[i] = max(dp[j-1]-sum[j])+sum[i]   j in [i-k,i]
        while (!dq.empty() && dq.front() < i - k) dq.pop_front();
        while (!dq.empty() && calc(dq.back()) <= calc(i)) dq.pop_back();
        dq.push_back(i);
        dp[i] = calc(dq.front()) + sum[i];
    }
    printf("%lld\n", dp[n]);
    return 0;
}