题解 | #C悲伤的RT#

C题-悲伤的RT，双向队列deque+dp

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
void my_ans(){
    long long i,n,m;
    cin>>n>>m;
    long long a[n+1], ans[n+1];
    for(i=1;i<=n;++i) cin>>a[i];
    ans[0] = 0;
    deque<pair<int,int>> que;
    pair<int,int> p;
    for(i=1;i<=n;++i){
        ans[i] = ans[i-1];
        while(que.size()>0 && que.back().first >= a[i])
            que.pop_back();
        while(que.size()>0 && que.front().second <= i-m)
            que.pop_front();
        p.first = a[i];p.second = i;
        que.push_back(p);
        if (i-m>=0 && ans[i] < ans[i-m] + que.front().first)
            ans[i] = ans[i-m] + que.front().first;
    }
    cout<<ans[n]<<endl;
    return;
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t=1,i,j;
    //cin>>t;
    while(t>0){
        --t;my_ans();
    }
    return 0;
}
// 64 位输出请用 printf("%lld")