蜜汁UKE

TRZ_2007 @ 2020-08-02 15:22:51

#include <bits/stdc++.h>
using namespace std;

const int N = 200009;

int a[N],n,l,r;
int f[N],q[N],ans = INT_MIN;
int head = 1,tail;

void pop(int id) {
    while(head <= tail) {
        if(q[head] + r < id) head++;
        else break;
    }
}

void push(int id) {
    while(head <= tail) {
        if(f[id] >= f[q[tail]]) tail--;
        else break;
    }
    q[++tail] = id;
}

int main() {
    scanf("%d %d %d",&n,&l,&r);
    for(int i = 0;i <= n;i++) {
        scanf("%d",&a[i]);
        f[i] = -19260817;
    }
    f[0] = 0;
    for(int i = l;i <= n;i++) {
        push(i - l);
        pop(i);
        f[i] = f[q[head]] + a[i];
    }
    for(int i = n - r + 1;i <= n;i++) ans = max(ans,f[i]);
    printf("%d\n",ans);
    return 0;
}

by 俞嘉轶 @ 2020-08-02 15:23:28

干得漂亮

by TRZ_2007 @ 2020-08-02 15:25:05

@hanyufei
@jiangchenhe_2008
@\color{black}\texttt{c}\color{red}\texttt{henxinyang2006}

by TRZ_2007 @ 2020-08-02 15:29:56

好了，没事了

by 俞嘉轶 @ 2020-08-02 15:30:01

t=1

by _StarBird_ @ 2020-08-02 16:04:35

@TRZ_2007 Orz

by _StarBird_ @ 2020-08-02 16:04:43

@俞嘉轶 ?

by 程义轩 @ 2020-10-24 11:48:34

#include <bits/stdc++.h>
using namespace std;
int a[200005];
int f[200005];
int q[200005], head = 1, tail;
int n, l, r;
int main() {
    cin >> n >> l >> r;
    for (int i = 0; i <= n; i++) {
        cin >> a[i];
    }
    memset(f, 0xcf, sizeof(f));
    int ans = f[0];
    f[0] = 0;
    int j = 0;
    for (int i = l; i <= n; i++) {
        while (head <= tail && f[q[tail]] < f[j]) 
            tail--;
         q[++tail] = j;
        if (q[tail] - q[head] > r - l) 
            head++;
        f[i] = f[q[head]] + a[i];
        j++;
    }
    for (int i = n - r + 1; i <= n; i++) {
        ans = max(ans, f[i]);
    }

    cout << ans << endl;
    return 0;
}