震惊!单调队列的代码居然会产生30号混凝土!

P2627 [USACO11OPEN] Mowing the Lawn G

lhz2022 @ 2024-10-06 10:59:01

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define debug() puts("I WILL AK")
#define N 100007
int a[N],b[N],dp[N],que[N],ll,rr,n,m;
signed main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        b[i]=b[i-1]+a[i];
    }
    for(int i=1;i<=n;++i){
        dp[i]=dp[que[ll]-1]-b[que[ll]]+b[i];
        while(ll<=rr&&dp[que[rr]-1]-b[que[rr]]<=dp[i]-b[i+1]){
            rr--;
        }
        que[++rr]=i;
        while(ll<=rr&&que[rr]-que[ll]>=m) ++ll;
    }
    cout<<dp[n];
    return 0;
}

by lhz2022 @ 2024-10-06 10:59:31

30pts求条


by __Tonycyt__ @ 2024-10-06 11:02:17

btd


|