求调

Xianzi_ @ 2024-10-13 16:02:07

#include "bits/stdc++.h"
using namespace std;
int n, l, r;
int h = 1, t = 0, ans = INT_MIN;
int a[200005], dp[200005], q[200005];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> l >> r;
    for (int i = 0; i <= n; i++) cin >> a[i];
    for (int i = 0; i <= n; i++){
        //do head
        while (q[h] < i - r && h <= t) h++;
        //do tail
        while (dp[q[t]] < dp[i - 1] && h <= t) t--;
        q[++t] = i - 1;
        dp[i] = dp[q[h]] + a[i];
        cout << "dp[" << i << "] = " << dp[i] << endl;
        if (i + r > n) ans = max(ans, dp[i]);
    }
    cout << ans;
    return 0;
}

by fairfriendZ @ 2024-10-13 16:09:54

=i吧

by fairfriendZ @ 2024-10-13 16:11:03

q[++t]=i

by XYstarabyss @ 2024-10-13 16:43:50

改了两年半

#include "bits/stdc++.h"
using namespace std;
int n, l, r;
int h = 1, t = 1, ans = INT_MIN;
int a[300005], dp[300005], q[300005];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> l >> r;
    for (int i = 0;i <= n + r; i++){
        dp[i] = INT_MIN;
    }
    for (int i = 0; i <= n; i++){
        cin >> a[i];
    }
    dp[0] = 0;
    for (int i = l; i <= n + r; i++){
        //do tail
        while(dp[i - l] >= dp[q[t]] && t >= h) t --;
        q[++t] = i - l;//入队 
        //do head
        while(q[h] + r < i) h ++;
        dp[i] = dp[q[h]] + a[i];
        //cout << "dp[" << i << "] = " << dp[i] << endl;
        if (i + r > n) ans = max(ans, dp[i]);
    }
    cout << ans;
    return 0;
}