$修剪草坪$修剪草坪

题目描述见链接 .

$正解部分$正解部分

连续的工作的牛不超过 $K$K 个 $\to$→ 第 $i$i 头牛若工作, 则左边与其 相距最近的不工作的牛 坐标范围为 $[i-K,i]$[i−K,i] .
所以可以想到 $dp$dp, 设 $F[i,1/0]$F[i,1/0] 表示前 $i$i 头牛, 第 $i$i 头牛 工作/不工作 所能得到的最大价值,
$状态转移$状态转移:
$F[i,0]=\max \left(F\right[i-1,0],F[i-1,1\left]\right)F[i,1]=\max \left(F\right[j,0]+sum[i]-sum[j\left]\right)=\max \left(F\right[j,0]-sum[j\left]\right)+sum\left[i\right](j\in [i-K,i\left]\right)$F[i,0]=max(F[i−1,0],F[i−1,1])F[i,1]=max(F[j,0]+sum[i]−sum[j])=max(F[j,0]−sum[j])+sum[i]      (j∈[i−K,i])
其中 $F[i,0]-sum\left[j\right]$F[i,0]−sum[j] 可以使用 单调队列 优化 .

$实现部分$实现部分

#include<bits/stdc++.h>
#define reg register
typedef long long ll;

const int maxn = 1e5 + 5;

int N;
int K;
int A[maxn];

ll sum[maxn];
ll F[maxn][2];

int main(){
        scanf("%d%d", &N, &K);
        for(reg int i = 1; i <= N; i ++) scanf("%d", &A[i]), sum[i] = sum[i-1] + A[i];
        std::deque <int> Q;
        Q.push_front(0);
        for(reg int i = 1; i <= N; i ++){
                F[i][0] = std::max(F[i-1][0], F[i-1][1]);
                int l = std::max(0, i-K);
                while(!Q.empty() && Q.front() < l) Q.pop_front();
                if(Q.empty()) F[i][1] = A[i];
                else F[i][1] = F[Q.front()][0] - sum[Q.front()] + sum[i];
                while(!Q.empty() && F[Q.back()][0] - sum[Q.back()] <= F[i][0] - sum[i]) Q.pop_back();
                Q.push_back(i);
        }
        printf("%lld\n", std::max(F[N][0], F[N][1]));
        return 0;
}