修剪草坪

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1093 字

N头奶牛排成一排，选若干头使效率之和最大，且

一本通
例

正文

/*
原题：T1599 「一本通 5.5 例 3」修剪草坪
题意：N 头奶牛排成一排，选若干头使效率之和最大，且任意连续被选的牛不超过 K 头。
思路：dp[i] 表示前 i 头的最大效率；不取 i 则 dp[i]=dp[i-1]，
     取 i 则接一段长度≤K 的块，块前一头不取（或块从第 1 头开始）。
     用单调队列维护 (dp[j]-s[j+1]) 的滑动窗口最大值（窗口长 K+1）。
复杂度：时间 O(N)，空间 O(N)。
易错点：块可从第 1 头开始（对应虚拟 j=-1，值取 0）；队列维护“最大”而非最小；用 long long。
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,K;
    cin>>N>>K;
    vector<long long> a(N+1),s(N+1,0);
    for(int i=1;i<=N;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    vector<long long> dp(N+1,0);
    deque<int> q;
    q.push_back(0);
    for(int i=1;i<=N;i++){
        int L=i-K-1;
        while(!q.empty()&&q.front()<L){
            q.pop_front();
        }
        long long best=q.empty()?(LLONG_MIN):(dp[q.front()]-s[q.front()+1]);
        if(i<=K){
            best=max(best,0LL);
        }
        dp[i]=max(dp[i-1],s[i]+best);
        while(!q.empty()&&(dp[q.back()]-s[q.back()+1])<=(dp[i]-s[i+1])){
            q.pop_back();
        }
        q.push_back(i);
    }
    cout<<dp[N]<<'\n';
    return 0;
}

修剪草坪

正文

一本通·提高篇的其它内容