单调栈和单调队列优化DP

luogu P1725 琪露诺

一道比较板的题
明显是一个DP，则有

如果暴力则为 \(O(n^2)\)

但是发现 \(\max_{j=i-r}^{i-l}dp_j\) 就是单调队列所解决的问题，所以直接单调队列维护即可

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 2e5 + 5;
int n, l, r;
ll a[N], dp[N];
deque<int> q;
int main() {
    // FASTIO;
    cin >> n >> l >> r;
    memset(dp, 128, sizeof dp);
    for (int i = 0; i <= n; i++) {
        cin >> a[i];
        // if (i <= l - 1) dp[i] = a[i];
    }
    dp[0] = a[0];
    q.push_back(0);
    ll ans = -1e9 - 7;
    for (int i = l; i <= n; i++) {
        while (!q.empty() && dp[q.back()] < dp[i - l]) q.pop_back();
        q.push_back(i - l);
        while (q.front() + r < i) q.pop_front();
        if (q.size()) dp[i] = dp[q.front()] + a[i];
        if (i + r > n) ans = max(ans, dp[i]);
    }
    cout << ans;
    return 0;
}