单调队列优化dp 求调

记录

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

const int N = 1e6;

int n,k,a[N];
int add[N],f[N],q[N]; 
deque<int> dq;

signed main() {
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) add[i]=add[i-1]+a[i];

    int ans=0;
    dq.push_back(0);
    for(int i=1;i<=n;i++) {
        f[i]=a[i];
        f[i]=max(f[i],q[dq.front()-1]-add[dq.front()]+add[i]);
        q[i]=max(f[i],q[i-1]);
        ans=max(ans,f[i]);
        int x=q[i-1]-add[i];

        while(!dq.empty()&&q[dq.front()-1]-add[dq.front()]<=x) dq.pop_front();
    while(!dq.empty()&&dq.front()+k<=i) dq.pop_front(); dq.push_back(i);
    }
    cout<<ans;
    return 0;
}