1 专题说明

本专题用来记录使用单调队列的DP问题。

2 训练

题目1：135最大子序和

C++代码如下，

#include <iostream>
#include <vector>
#include <deque>
#include <climits>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> nums(n + 1);
    for (int i = 1; i <= n; ++i) cin >> nums[i];
    
    vector<int> s(n + 1);
    for (int i = 1; i <= n; ++i) s[i] += s[i-1] + nums[i];
    
    int res = INT_MIN;
    deque<int> q;
    for (int i = 1; i <= n; ++i) {
        //对于数组nums,求下标从i-m+1,..,i-1,i这个子区间中的连续子数组的最大值
        //对于数组s,求下标从i-m,i-m+1,...,i-1滑动区间内的最小值
        
        while (!q.empty() && q.front() < i - m) q.pop_front();
        
        while (!q.empty() && s[q.back()] >= s[i-1]) q.pop_back();
        
        q.push_back(i-1);
        
        res = max(res, s[i] - s[q.front()]);
        
    }
    cout << res << endl;
    
    return 0;
}

题目2：1088旅行问题

C++代码如下，

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 2e6 + 10;

int n;
int oil[N], dist[N];
LL s[N];
int q[N];
bool ans[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &oil[i], &dist[i]);
        s[i] = s[i + n] = oil[i] - dist[i];
    }
    for (int i = 1; i <= n * 2; ++i) s[i] += s[i - 1];
    
    int hh = 0, tt = 0;
    q[0] = n * 2 + 1;
    for (int i = n * 2; i >= 0; --i) {
        if (q[hh] > i + n) hh++;
        if (i < n) {
            if (s[i] <= s[q[hh]]) ans[i + 1] = true;
        }
        while (hh <= tt && s[q[tt]] >= s[i]) tt--;
        q[++tt] = i;
    }
    
    dist[0] = dist[n];
    for (int i = 1; i <= n; ++i) s[i] = s[i + n] = oil[i] - dist[i - 1];
    for (int i = 1; i <= n * 2; ++i) s[i] += s[i - 1];
    
    hh = 0, tt = 0;
    q[0] = 0;
    for (int i = 1; i <= n * 2; ++i) {
        if (q[hh] < i - n) hh++;
        if (i > n) {
            if (s[i] >= s[q[hh]]) ans[i - n] = true;
        }
        while (hh <= tt && s[q[tt]] <= s[i]) tt--;
        q[++tt] = i;
    }
    
    for (int i = 1; i <= n; ++i) {
        if (ans[i]) puts("TAK");
        else puts("NIE");
    }
    
    return 0;
}

题目3：1089烽火传递

C++代码如下，

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10, INF = 1e9;

int n, m;
int w[N], q[N];
int f[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
    
    int hh = 0, tt = 0;
    for (int i = 1; i <= n; ++i) {
        if (q[hh] < i - m) hh++;
        f[i] = f[q[hh]] + w[i];
        while (hh <= tt && f[q[tt]] >= f[i]) tt--;
        q[++tt] = i;
    }
    
    int res = INF;
    for (int i = n - m + 1; i <= n; ++i) res = min(res, f[i]);
    
    printf("%d\n", res);
    
    return 0;
}

题目4：1090绿色通道

C++代码如下，

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 50010, INF = 1e9;

int n, m;
int w[N];
int f[N], q[N];

bool check(int k) {
    f[0] = 0;
    int hh = 0, tt = 0;
    for (int i = 1; i <= n; ++i) {
        if (hh <= tt && q[hh] < i - k - 1) hh++;
        f[i] = f[q[hh]] + w[i];
        while (hh <= tt && f[q[tt]] >= f[i]) tt--;
        q[++tt] = i;
    }
    
    int res = INF;
    for (int i = n - k; i <= n; ++i) res = min(res, f[i]);
    
    return res <= m;
}

int main () {
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
    
    int l = 0, r = n;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    
    printf("%d\n", r);
    
    return 0;
}

题目5：1087修剪草坪

C++代码如下，

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int n, m;
LL s[N];
LL f[N];
int q[N];

LL g(int i) {
    if (!i) return 0;
    return f[i - 1] - s[i];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
    }
    
    int hh = 0, tt = 0;
    for (int i = 1; i <= n; ++i) {
        if (q[hh] < i - m) hh++;
        f[i] = max(f[i - 1], g(q[hh]) + s[i]);
        while (hh <= tt && g(q[tt]) <= g(i)) tt--;
        q[++tt] = i;
    }
    
    printf("%lld\n", f[n]);
    
    return 0;
}

题目6：1091理想的正方形

C++代码如下，

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, INF = 1e9;

int n, m, k;
int w[N][N];
int row_min[N][N], row_max[N][N];
int q[N];

void get_min(int a[], int b[], int tot) {
    int hh = 0, tt = -1;
    for (int i = 1; i <= tot; ++i) {
        if (hh <= tt && q[hh] <= i - k) hh++;
        while (hh <= tt && a[q[tt]] >= a[i]) tt--;
        q[++tt] = i;
        b[i] = a[q[hh]];
    }
}

void get_max(int a[], int b[], int tot) {
    int hh = 0, tt = -1;
    for (int i = 1; i <= tot; ++i) {
        if (hh <= tt && q[hh] <= i - k) hh++;
        while (hh <= tt && a[q[tt]] <= a[i]) tt--;
        q[++tt] = i;
        b[i] = a[q[hh]];
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            scanf("%d", &w[i][j]);
        }
    }
    
    for (int i = 1; i <= n; ++i) {
        get_min(w[i], row_min[i], m);
        get_max(w[i], row_max[i], m);
    }
    
    int res = INF;
    int a[N], b[N], c[N];
    for (int i = k; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) a[j] = row_min[j][i];
        get_min(a, b, n);
        
        for (int j = 1; j <= n; ++j) a[j] = row_max[j][i];
        get_max(a, c, n);
        
        for (int j = k; j <= n; ++j) res = min(res, c[j] - b[j]);
    }
    
    printf("%d\n", res);
    
    return 0;   
}

参考

acwing