P1725 琪露诺 题解(单调队列)
2024-09-08 08:14:27
题目链接
解题思路
单调队列优化的\(dp\)。
状态转移方程:\(f[i]=max{f[i-l],f[i-l+1],...,f[i-r-1],f[i-r]}+a[i]\)
考虑单调队列优化。
因为刚学,不是很熟悉单调队列,特写一篇详细的解释。
\(queue\) 数组存储一个队列,他的头部和尾部的下标分别用head和tail表示。
\(f\) 数组是\(dp\)用到的数组。
首先读入每一个坐标处的价值\(a[i]\)
枚举\(i\),从\(l\)到\(n\),分别计算\(f[i]\),当\(i+r>n\)时,存储最大值ans。
单调队列的注释写在代码中。
AC代码
#include<stdio.h>
int i,n,l,r,a[200010],f[200010],ans=-2147483648;//这个题数据比较水,ans=0也能过,但理论上是不允许这样的
int queue[200010],head=0,tail=-1;
int main(){
scanf("%d%d%d",&n,&l,&r);
for(i=0;i<n;i++){
scanf("%d",&a[i]);
}
for(i=l;i<=n;i++){
while(head<=tail&&queue[head]+r<=i)head++;//如果头太靠前了,那就删掉
while(head<=tail&&f[queue[tail]]<=f[i-l])tail--;//如果尾巴对应的a太小了,那就删掉
//这两句保证了单调队列的不上升也即单调减特性,保证头永远是当前状态的最佳状态
queue[++tail]=i-l;//存储上一次是从哪里来的
f[i]=a[i]+f[queue[head]];//从上一步跳过来,跳到这里的最大值
if(i>n-r&&f[i]>ans)ans=f[i];
}
printf("%d",ans);
return 0;
}
最新文章
- 2016/11/16 周三 <;使用LocalStore记住用户密码方法示例>;
- oracle in VS or效率
- win7&;win8.1 x64位系统下在VS2010下配置MPICH2&;测试&;解决scanf不能输入
- border-width和border其它属性配合实现的小三角形标签效果
- 用js 向h5 中的table 动态添加数据 (简单实现)
- Codeforces 620E New Year Tree(DFS序 + 线段树)
- MySQL常用SQL/函数汇总(持续更新)
- Java:多线程
- HDU4907——Task schedule(BestCoder Round #3)
- 手动开启tomacat服务器
- CELERY里,这个WARNING如何消除?
- xcode升级后, 插件失效修复
- HDOJ/HDU 2562 奇偶位互换(交换位置~)
- Could not drop object &;#39;student&;#39; because it is referenced by a FOREIGN KEY constraint
- Visual Studio Team Services使用教程--邀请团队成员
- springcloud(一):大话Spring Cloud
- VUE-CLI Vue安装及开发,npm run build无法查看项目的问题
- shell第三篇
- 【Tyvj 1728】普通平衡树
- P1313 计算系数 HMR大佬讲解