ConanKIDの小窝

ConanKIDの小窝

单调队列优化DP学习笔记

posted on 2021-08-20 10:07:16 | under 学习笔记 |

先来看

考虑DP。设$dp_{i,0/1}$表示第$i$个数选或不选时,前$i$个数的最大结果。显然有状态转移方程:

$$dp_{i,0}=\max\{dp_{i-1,0},dp_{i-1,1}\}$$

$$dp_{i,1}=\max\limits_{i-k\le j\le i-1}\{dp_{j,0}+(sum_i-sum_j)\}$$

其中$sum$表示前缀和。

但是朴素计算的复杂度是$O(n^2)$的,因此必须优化。

将状态转移方程变形:

$$dp_{i,1}=\max\limits_{i-k\le j\le i-1}\{dp_{j,0}-sum_j\}+sum_i$$

我们发现,当$i$增加$1$时,$j$的取值的上界和下界均会增加$1$。这个形式就长得很像滑动窗口了。

因此,我们可以用一个单调队列,维护$dp_{j,0}-sum_j$的最大值。这样一来,总时间复杂度就是维护单调队列的复杂度,即$O(n)$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, k;
int a[100005], sum[100005];
int dp[100005][2], q[100005];
int l, r;
int calc(int x) {return dp[x][0] - sum[x];}
signed main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i], sum[i] = sum[i - 1] + a[i];
    l = r = 1; q[1] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
        while (l <= r && i - q[l] > k) l++;//排除队头“过期”的决策
        dp[i][1] = calc(q[l]) + sum[i];//直接取出队头计算
        while (l <= r && calc(i) >= calc(q[r])) r--;//维护单调性
        q[++r] = i;
    }
    cout << max(dp[n][0], dp[n][1]) << endl;
    return 0;
}

再来看这个

设$dp_{i,j}$表示前$i$个人刷前$j$块木板所能得到的最大价值。那么显然:

$$dp_{i,j}=\max\limits_{j-l_i\le k\le s_i-1}\{dp_{i-1,k}+p_i\times(j-k)\}$$

变形得

$$dp_{i,j}=p_i\times j+\max\limits_{j-l_i\le k\le s_i-1}\{dp_{i-1,k}-p_i\times k\}$$

我们把外层循环的$i$看做定值,那么随着$j$的增大,$k$的上界不变,下界增大。因此,我们也可以按照上题的方法,维护一个$dp_{i-1,k}-p_i\times k$单调递减的队列,从而将时间复杂度优化至$O(nm)$。

#include<iostream>
#include<algorithm>
using namespace std;
int n, m;
struct node {
    int p, l, s;
    bool operator < (const node &a) const {return s < a.s;}
} a[100005];//首先要把所有人按照s排序
int dp[105][100005], q[100005];
int l, r;
int calc(int i, int k) {return dp[i - 1][k] - a[i].p * k;}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> a[i].l >> a[i].p >> a[i].s;
    sort(a + 1, a + 1 + m);
    for (int i = 1; i <= m; i++) {
        l = 1, r = 0;//每次新建一个队列
        for (int k = max(0, a[i].s - a[i].l); k <= a[i].s - 1; k++) {
            while (l <= r && calc(i, q[r]) <= calc(i, k)) r--;
            q[++r] = k;
        }//将所有可能的决策入队
        for (int j = 1; j <= n; j++) {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);//第i个人可以什么都不刷,或第j块木板可以不刷
            if (j >= a[i].s) {
                while (l <= r && q[l] < j - a[i].l) l++;
                if (l <= r) dp[i][j] = max(dp[i][j], calc(i, q[l]) + a[i].p * j);
            }
        }
    }
    cout << dp[m][n] << endl;
    return 0;
}

一道经典题

很有意思的好题。考虑二分答案,问题转化为当跳跃距离为$[d-x,d+x]$时能取得多少分数。这个东西就可以DP了。

设$dp_i$表示前$i$个格子能取得的最大分数,那么显然:

$$dp_i=\max\limits_{x_i-d-x\le x_j\le x_i-d+x}\{dp_j\}+s_i$$

注意到$x_i$是单调递增的,所以这个东西显然也是可以单调队列优化的。时间复杂度$O(n)$。

#include<bits/stdc++.h>
using namespace std;
int n, d, k;
int a[500005];
int s[500005];
int dp[500005];
int q[500005], l, r;
bool check(int x) {
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
        dp[i] = -1e9;
    int p = 0; l = 1, r = 0;
    for (int i = 1; i <= n; i++) {
        while (a[i] - a[p] >= max(1, d - x) && p < i) {//把状态i的所有可能决策入队
            if (dp[p] == -1e9) {p++; continue;}//p不可到达,则直接退出
            while (l <= r && dp[q[r]] <= dp[p]) r--;
            q[++r] = p++;//将p入队
        }
        while (l <= r && a[i] - a[q[l]] > d + x) l++;//排除队头“过期”决策
        if (l <= r) dp[i] = dp[q[l]] + s[i];
        if (dp[i] >= k) return 1;
    }
    return 0;
}
void work() {
    int l = -1, r = 5000001;
    while (l + 1 < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid;
    }//二分
    if (r != 5000001) cout << r << endl;
    else cout << -1 << endl;
}
int main() {
    cin >> n >> d >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> s[i];
    work();
    return 0;
}

Q:何时可以考虑单调队列优化DP?

A:状态转移方程遵循如下形式:

$$dp_i=\max\{dp_j+val(i,j)\}$$

其中$val$是一个仅与$i,j$中的一项有关的多项式。如果含$i,j$的乘积项的话,那就考虑斜率优化吧。


几道练习: