1、B站视频链接:E44 单调队列优化DP 修剪草坪_哔哩哔哩_bilibili
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int n,k,q[N];
LL w[N],f[N],sum;
int main(){
cin>>n>>k; k++; //
for(int i=1;i<=n;i++){
cin>>w[i];
sum+=w[i];
}
int h=1,t=0;LL ans=1e18;
for(int i=1;i<=n;i++){
while(h<=t && f[q[t]]>=f[i-1]) t--;
q[++t]=i-1;
if(q[h]<i-k) h++;
f[i]=f[q[h]]+w[i];
if(i>n-k) ans=min(ans,f[i]);
}
cout<<sum-ans;
}