luogu P3572 [POI2014]PTA-Little Bird
2024-10-07 14:56:40
题目描述
从1开始,跳到比当前矮的不消耗体力,否则消耗一点体力,每次询问有一个步伐限制,求每次最少耗费多少体力
单调队列优化动态规划
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
#define int long long
int a[N],dp[N],q[N],l,r=1;
int n,m,k;
inline void in(){
cin>>n;
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
cin>>m;
}
signed main(){
in();
while(m--){
scanf("%lld",&k);
l=r=1,q[r]=1;
for(int i=2;i<=n;i++){
while(l<=r&&i-q[l]>k)l++;
if(a[q[l]]>a[i])dp[i]=dp[q[l]];
else dp[i]=dp[q[l]]+1;
while(l<=r&&(dp[q[r]]>dp[i]||(dp[q[r]]==dp[i]&&a[q[r]]<=a[i])))r--;
q[++r]=i;
}
cout<<dp[n]<<endl;
}
}
最新文章
- 使用ArcGIS JavaScript API 3.18 加载天地图
- cacti结合nagios
- 【转】一个不错的eclipse反编译插件
- java jps命令
- 技术小白:Hadoop 到底是啥?
- XmlSerializer
- 关于mysql中触发器old和new如何更好的区别我有话要说?
- 【less和sass的区别,你了解多少?】
- 【Beta】 第二次Daily Scrum Meeting
- myeclipse将java项目转换成web项目,导出war包
- java中的构造,封装
- gevent:异步理论与实战[转]
- Django:django-cors-headers 报错no module named ";corsheaders";
- Eclipse中Git的使用以及IDEA中Git的使用
- java算法----排序----(5)归并排序
- JVM——Java HotSpot VM Options
- java 迭代
- Volley封装
- Ubuntu 开机自动启动
- 微网站|h5弹窗|手机网站 html5 弹窗、弹层、提示框、加载条
热门文章
- 持续集成Gitlab CICD Runner&;Jenkins
- 『题解』Coderforces352A Jeff and Digits
- C语言程序设计100例之(4):水仙花数
- 推荐Java五大微服务器及其代码示例教程
- 03-MyBatis拦截器机制
- spark集群搭建(三台虚拟机)——zookeeper集群搭建(3)
- nyoj 283-对称排序 (sort)
- expect 自动填充密码
- 某些机root也不能访问dma-buf
- 执行yaml.load()出现警告信息:YAMLLoadWarning: callingyaml.load() without Loader=..