为什么谜一样的WA9个点?我已经方了

P2627 [USACO11OPEN] Mowing the Lawn G

BeyondStars @ 2018-12-31 20:11:52

Rt

//
// Created by dhy on 18-12-31.
//
#include <iostream>
#include <deque>
using namespace std;
long long F[100010];
long long s[100010];
long long work(int j){return F[j-1]-s[j];}
int main(){
    long long N,K;
    cin>>N>>K;
    for(int i = 1;i<=N;i++){cin>>s[i];s[i]+=s[i-1];}
    deque<int> q;
    for(int i = 1;i<=N;i++){
        while(!q.empty()&&work(q.back())<=work(i))
            q.pop_back();
        q.push_back(i);
        while(!q.empty()&&q.front()<=i-K-1)
            q.pop_front();
        F[i] = work(q.front())+s[i];
    }
    cout<<F[N];
    return 0;
}

by BeyondStars @ 2018-12-31 20:54:35

我懂了,忘了在单调队列里面维护初始状态


|