洛谷P2627 [USACO11OPEN]Mowing the Lawn G (单调队列优化DP)
2022/6/11 23:50:52
本文主要是介绍洛谷P2627 [USACO11OPEN]Mowing the Lawn G (单调队列优化DP),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一道单调队列优化DP的入门题。
f[i]表示到第i头牛时获得的最大效率。
状态转移方程:f[i]=max(f[j-1]-sum[j])+sum[i] ,i-k<=j<=i。j的意义表示断点,因为不能连续安排超过k只牛,肯定要在中间断开一处。
max中f[j-1]-sum[j]只和j相关,我们可以对其做递减单调队列,最后队头就是最大值max。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N=1e5+10; 5 ll n,m,sum[N],f[N],d[N]; 6 int q[N],head=0,tail=1; 7 ll que(int i){ 8 d[i]=f[i-1]-sum[i]; 9 while(head<=tail&&d[q[tail]]<d[i]) tail--;//将d[i]插入队列中 10 q[++tail]=i; 11 while(head<=tail&&q[head]<i-m) head++; 12 return d[q[head]]; 13 } 14 15 int main(){ 16 scanf("%lld%lld",&n,&m); 17 for(int i=1;i<=n;i++) scanf("%lld",&sum[i]),sum[i]+=sum[i-1]; 18 for(int i=1;i<=n;i++) f[i]=que(i)+sum[i]; 19 printf("%lld",f[n]); 20 }
这篇关于洛谷P2627 [USACO11OPEN]Mowing the Lawn G (单调队列优化DP)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain
- 2024-06-19EntBot.ai: AI Website Chatbot for Product Guides and Development Doc
- 2024-06-17zero-shot-learning-definition-examples-comparison
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置