#单调队列，动态规划#洛谷 2627 jzoj 2202 2321（高中）codevs 4654 修剪草坪

本文主要是介绍#单调队列，动态规划#洛谷 2627 jzoj 2202 2321（高中）codevs 4654 修剪草坪，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

在n头奶牛里选择若干头，使连续的奶牛不超过k头并让总价值最大。

---

分析

这道题正向选择比较难选，所以就想到了n头奶牛都选并去掉奶牛后使总价值最大。
用单调队列维护，时间复杂度O（n）

---

代码

#include <cstdio>
#include <cctype>
using namespace std;
typedef long long ll;
ll n,k,l,r,q[100001],ans,a[100001],f[100001];
ll in(){ll ans=0; char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
ll max(ll a,ll b){return (a>b)?a:b;}
int main(){n=in(); k=in(); ll l=1,r=1;for (ll i=1;i<=n;i++) ans+=(a[i]=in());for (ll i=1;i<=n;i++){while (l<=r&&q[l]<i-k-1) l++;f[i]=a[i]+f[q[l]];while (l<=r&&f[q[r]]>=f[i]) r--;q[++r]=i;}for (ll i=n-k;i<n;i++) f[i+1]=(f[i+1]<f[i])?f[i+1]:f[i];return !printf("%lld",ans-f[n]);
}

这篇关于#单调队列，动态规划#洛谷 2627 jzoj 2202 2321（高中）codevs 4654 修剪草坪的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---