洛谷P2627 [USACO11OPEN]Mowing the Lawn G (单调队列优化DP)
2024-09-02 00:13:09
一道单调队列优化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 }
最新文章
- Uva 11732 strcmp() Anyone?
- Fragment配合RadioGroup实现点击切换布局
- DateTime , DateTime2 ,DateTimeOffset 之间的小区别
- sql 读取本地txt文件批量插入数据库
- mysql性能瓶颈分析、性能指标、指标搜集方法与性能分析调优工具
- Hrbustoj 1429 二分+计算几何
- 161021、spring异步调用,完美解决!
- java.util.concurrent
- JS概念
- python的生成器
- Minimum Size Subarray Sum —— LeetCode
- RMAN备份之非归档模式下的备份
- C#后台发送HTTP请求
- 海美迪Q系列视频文明书
- 线程androidAndroid ConditionVariable的用法
- 作用域链和函数内部this指向问题以及bind、call、apply方法
- Zepto源码分析之二(新旧版本zepto.Z方法的区别)
- shell脚本修改文本中匹配行之前的行的方法
- linux中,当执行rpm -e删除一个软件包时,都做了些什么事
- Beanshell断言