动态规划（算法竞赛、蓝桥杯）--单调队列优化修建草坪

本文主要是介绍动态规划（算法竞赛、蓝桥杯）--单调队列优化修建草坪，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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;
}

 

 

这篇关于动态规划（算法竞赛、蓝桥杯）--单调队列优化修建草坪的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---