0%

单调队列优化dp

发表于 更新于 分类于

单调队列主要用于求连续子区间的最值，可以将大大降低dp中的复杂度。

在运用上，我们发现单调队列优化的几个特点：

  1. 所求区间所需变量相对独立，有其它变量的话，转移时能够分离
  2. 枚举区间时，所求区间的所有元素必须进入过队列
  3. 超出枚举区间的元素应被及时剔除

下面给出几个栗子

CF940E Cashback

#简要做法

不难发现，如果将一段分成长度为$k=a\cdot c+b$的一段，其结果只会劣于将相同区间分成$a$段长度为$c$的和$b$段1的。用这个特点，我们可以推出dp式子：

​ $f[i]=min(f[i-1]+a[i],f[i-c]+\sum_{k=i-c+1}^{i}a[i]-min(a[i-c+1],a[i-c+2],……,a[i]))$

其中区间求min的过程用单调队列优化，可以把复杂度从$O(n^2)$降到$O(n)$

Code

#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 5;
int n, c;
ll a[maxn], s[maxn], q[maxn], f[maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> c;
    for(int i = 1; i <= n; ++i)
        cin >> a[i], s[i] = s[i - 1] + a[i];
    ll tmp, l = 1, r = 0;
    for(int i = 1; i <= n; ++i) {
        while(l <= r && a[i] < a[q[r]]) r--;
        while(l <= r && i - q[l] >= c) l++;
        q[++r] = i;
        tmp = 1e18;
        if(i >= c) 
            tmp = f[i - c] + s[i] - s[i - c] - a[q[l]];
        f[i] = min(f[i - 1] + a[i], tmp);
    }
    cout << f[n];
    return 0;
}

「SWTR-03」Golden Sword

#简要做法

考虑$f[n][m]$放入前n种材料，里面有m个，那么dp式子：

​ $f[i][j]=max(f[i-1][j-1],f[i-1][j],……,f[i-1][j+s-1])+a[i]\cdotj$

自然想到单调队列优化。这里有一个小技巧，就是因为枚举区间是在j以后，为了方便枚举，倒着加入单调队列即可不漏掉情况（因为用单调队列求最值必须保证所有要枚举的量进入过队列）。否则还需要在加入单调队列前先提前加入一部分元素。

Code

#pragma GCC optimize (3, "Ofast", "inline")
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 5505;
int n, w, s;
ll a[maxn], q[maxn], f[2][maxn];//滚动数组
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> w >> s;
    for(int i = 0; i <= w; ++i) f[0][i] = f[1][i] = -1e18;
    f[0][0] = 0;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) {
        int l = 1, r = 0;
        if(i == 2) f[0][0] = -1e18;
        for(int j = min(w, i); j; --j) {
            while(l <= r && q[l] > j + s - 1) l++;//超出范围则去掉
            while(l <= r && f[!(i & 1)][q[r]] < f[!(i & 1)][j]) r--;//不单调则去除
            q[++r] = j;
            f[i & 1][j] = max(f[!(i & 1)][j - 1], f[!(i & 1)][q[l]]) + a[i] * j;
        }
    }
    ll ans = -1e18;
    for(int i = 0; i <= w; ++i)
        ans = max(ans, f[n & 1][i]);
    cout << ans;
    return 0;
}

CF372C Watching Fireworks is Fun

#简要做法

比较套路的一个单调队列优化，dp式子显然是:

​ $f[i][j]=max(f[i-1][k])+b-|j-a|(j-len<=k<=j+len)$

第一维同样可以用滚动数组干掉

注意把控好区间边界，特判一下t相同的情况即可。

Code

#pragma GCC optimize (3, "Ofast", "inline")
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 150005;
int n, m, d;
ll f[2][maxn], q[maxn], l, r;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> m >> d;
    ll tt = 1, len;
    for(int i = 1; i <= m; ++i) {
        int a, b, t;
        cin >> a >> b >> t;
        len = (t - tt) * d, tt = t;
        l = 1, r = 0;
        if(!len) {
            for(int j = 1; j <= n; ++j)
                f[i & 1][j] = f[!(i & 1)][j] + b - abs(j - a);
            continue;
        }
        for(int j = 1; j <= min(len, 1ll * n); ++j) {
            while(l <= r && f[!(i & 1)][q[r]] < f[!(i & 1)][j]) r--;
            q[++r] = j;
        }
        for(int j = 1; j <= n; ++j) {
            if(j + len <= n) {
                while(l <= r && f[!(i & 1)][q[r]] < f[!(i & 1)][j + len]) r--;
                q[++r] = j + len;
            }
            while(l <= r && j - len > q[l]) l++;
            f[i & 1][j] = f[!(i & 1)][q[l]] + b - abs(j - a);
        }
    }
    ll ans = -1e18;
    for(int i = 1; i <= n; ++i)
        ans = max(ans, f[m & 1][i]);
    cout << ans;
    return 0;
}

[NOI2005]瑰丽华尔兹

#简要做法

很巧妙的一道题

正常情况想到$f[i][j][k]=max(f[i-1][j][k],f[i-1][j’][k’]+1)$ —> TLE+MLE

紧接着发现给出的是滑动区间，考虑$f[k][i][j]$是第k段区间，(i,j)的最大滑动距离：

​ $f[k][i][j]=max(f[k-1][i’][j’]+dis((i,j),(i’,j’)))$其中(i’,j’)是可能的起始点。

仍然TLE，于是想到max结构可以用单调队列优化，复杂度降到$O(kn^2)$，于是可以过了

Code

#pragma GCC optimize (3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
const int maxn = 205;
const int dx[5] = {0, -1, 1, 0, 0}, dy[5] = {0, 0, 0, -1, 1};
int n, m, X, Y, k;
char s[maxn][maxn];
int f[maxn][maxn], q[maxn], site[maxn], ans;
void solve(int x, int y, int len, int d) {//起始点为(x,y) 最多滑动len 方向d
    int head = 1, tail = 0;
    for(int i = 1; x <= n && x && y <= m && y; ++i, x += dx[d], y += dy[d]) {
        if(s[x][y] == 'x') head = 1, tail = 0;//遇到障碍物则清空队列
        else {
            while(head <= tail && f[x][y] > q[tail] + i - site[tail]) tail--;
            //如果从tail处的滑到(x,y)，f[x][y]仍然更优，那么要f[x][y]
            q[++tail] = f[x][y], site[tail] = i;//记录入队列时的位置，方便判断
            while(head <= tail && site[tail] - site[head] > len) head++;
            f[x][y] = q[head] + i - site[head];
            ans = max(ans, f[x][y]);
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> m >> X >> Y >> k;
    memset(f, 0xf3, sizeof(f));
    f[X][Y] = 0;
    for(int i = 1; i <= n; ++i)
        cin >> s[i] + 1;
    for(int i = 1; i <= k; ++i) {
        int d, l, r;
        cin >> l >> r >> d;
        int len = r - l + 1;
        if(d == 1) for(int j = 1; j <= m; ++j) solve(n, j, len, d);
        if(d == 2) for(int j = 1; j <= m; ++j) solve(1, j, len, d);
        if(d == 3) for(int j = 1; j <= n; ++j) solve(j, m, len, d);
        if(d == 4) for(int j = 1; j <= n; ++j) solve(j, 1, len, d);
    }
    cout << ans;
    return 0;
}