P1725 琪露诺

题目

P1725 琪露诺

算法标签: 单调队列优化$dp$

思路

首先最容易想的状态表示$f[i]$表示到达当前位置能够得到的最大价值, 直接暴力进行状态转移时间复杂度是$O(n^2)$, 但是数据范围是$10^5$会超时, 因此需要进行优化, 注意到每次当前装填都由上一个区间的最大值转移过来, 也就是求动态的区间最大值, 可以使用单调队列进行优化求解, 算法时间复杂度$O(n)$

代码

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

using namespace std;

const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;

int n, l, r, w[N];
int f[N];
int q[N], h = 0, t = -1;

void insert(int idx) {
   
    while (h <= t && f[q[t]] <= f[idx]) t--;
    q[++t] = idx;
}

int query(int idx) {
   
    while (h <= t && q[h] < idx - r) h++;
    return h <= t ? q[h] : -1;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> l >> r;
    for (int i = 0; i <= n; ++i) cin >> w[i];
    
    memset(f, -0x3f, sizeof f);
    f[0] = w[0];

    int ans = -INF;
    for (int i = 1; i <= n; ++i) {
   
        if (i - l >= 0) insert(i - l);
        int idx = query(i);
        if (idx != -1) f[i] = f[idx] + w[i];
        if (i + r > n) ans = max(ans, f[i]);
    }

    cout << ans << "\n";
    return 0;
}