【双指针优化DP】The 2022 Hangzhou Normal U Summer Trials H
Problem - H - Codeforces
题意:

思路:
首先很明显是DP
因为只有1e6个站点,因此可以以站点作为阶段
注意到K很小,因此可以尝试把这个当作第二维
设dp[i][j]为到达第i个站点,已经花了j元钱的最小步数
然后就想了一个n^2的做法,枚举两个指针,第i个站点从第p个站点转移,讨论是走过来的还是骑过来的,计算贡献
但是这样n^2肯定超时,因此我们去考虑特殊性质来枚举上一个状态
特殊性质是,K很小,因此考虑去枚举这次花了l元钱到第i个站点
但是这样的话从什么位置转移过来就不知道了,因此需要预处理从位置和花的钱数的关系

Code:
#include <bits/stdc++.h>#define int long longusing namespace std;const int mxn=1e6+10;
const int mxv=1e6+10;
const int mod=1e9+7;int N,P,S,K;
int a[mxn],dp[mxn][6],lx[6];void solve(){cin>>N>>P>>S;for(int i=1;i<=N;i++) cin>>a[i];cin>>K;memset(dp,0x3f,sizeof(dp));for(int i=0;i<=K;i++) dp[1][i]=a[1],lx[i]=1,dp[0][i]=0;for(int i=1;i<=N;i++){for(int j=0;j<=K;j++){while(a[i]-a[lx[j]]>j*S) lx[j]++;dp[i][j]=dp[i-1][j]+a[i]-a[i-1];for(int l=1;l<=j;l++){dp[i][j]=min(dp[i][j],dp[lx[l]][j-l]);} }}int ans=1e9;for(int i=1;i<=N;i++) ans=min(ans,dp[i][K]+P-a[i]);cout<<ans<<'\n';
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;while(__--)solve();return 0;
}
相关文章:
【双指针优化DP】The 2022 Hangzhou Normal U Summer Trials H
Problem - H - Codeforces 题意: 思路: 首先很明显是DP 因为只有1e6个站点,因此可以以站点作为阶段 注意到K很小,因此可以尝试把这个当作第二维 设dp[i][j]为到达第i个站点,已经花了j元钱的最小步数 然后就想了一…...
[论文笔记] LLM数据集——金融数据集
一、chatglm_金融 ModelScope 魔搭社区 请将modelscope sdk升级到v1.7.2rc0,执行: pip3 install "modelscope1.7.2rc0" -f https://modelscope.oss-cn-beijing.aliyuncs.com/releases/repo.html # 方式1 git clone http://www.modelscope…...
在亚马逊平台,如何有效举报违规行为?
众所周知,在每个行业都有一些违规现象,甚至这些违规现象还会给自己带来利益方面的损失,一旦触犯到自己的利益的话,那自己是需要想办法解决的,想办法规避。 就拿开亚马逊店铺来说,比较容易遇到的就是产品侵…...
深度学习入门教学——神经网络
深度学习就是训练神经网络。 1、神经网络 举个最简单的例子,以下是一个使用线性回归来预测房屋价格的函数。这样一个用于预测房屋价格的函数被称作是一单个神经元。大一点的神经网络,就是将这些单个神经元叠加起来。例如:神经网络根据多个相…...
阿里Java开发手册~OOP 规约
1. 【强制】避免通过一个类的对象引用访问此类的静态变量或静态方法,无谓增加编译器解析成 本,直接用 类名 来访问即可。 2. 【强制】所有的覆写方法,必须加 Override 注解。 说明: getObject() 与 get 0 bject() 的问题。…...
【Mysql数据库面试01】内连接 左连接 右连接 全连接
【Mysql数据库】内连接 左连接 右连接 全连接 0.准备1.内连接1.1 SQL(不带where)1.2 SQL(带where)1.3总结 2.左连接2.1SQL(不带where)2.2SQL(带where)2.3总结 3.右连接3.1 SQL(不带where&#x…...
事务隔离:为什么你改了我还看不见
前提概要 你肯定不陌生,和数据库打交道的时候,我们总是会用到事务。最经典的例子就 是转账,你要给朋友小王转 100 块钱,而此时你的银行卡只有 100 块钱。 转账过程具体到程序里会有一系列的操作,比如查询余额、做加减法…...
吴恩达ChatGPT《LangChain Chat with Your Data》笔记
文章目录 1. Introduction2. Document Loading2.1 Retrieval Augmented Generation(RAG)2.2 Load PDFs2.3 Load YouTube2.4 Load URLs2.5 Load Notion 3. Document Splitting3.1 Splitter Flow3.2 Character Splitter3.3 Token Splitter3.4 Markdown Spl…...
https和http有什么区别
https和http有什么区别 简要 区别如下: https的端口是443.而http的端口是80,且二者连接方式不同;http传输时明文,而https是用ssl进行加密的,https的安全性更高;https是需要申请证书的,而h…...
振弦采集仪及在线监测系统完整链条的岩土工程隧道安全监测
振弦采集仪及在线监测系统完整链条的岩土工程隧道安全监测 近年来,随着城市化的不断推进和基础设施建设的不断发展,隧道建设也日益成为城市交通发展的必需品。然而,隧道建设中存在着一定的安全隐患,如地质灾害、地下水涌流等&…...
linux基础学习
1.day1 2.day2 1、VIM配置; 2、安装SSH,调用putty接入终端; 3、shell命令; *:匹配任意长度的字符 ?:匹配一个长度的字符 [...]:匹配其中指定的一个字符 [-]:匹配指定…...
android 前端常用布局文件升级总结(二)
问题一: android:name“android.support.v4.content.FileProvider” 报红 问题解决方案: 把xml布局文件里面: android.support.v4.content.FileProvider 更换成 androidx.core.content.FileProvider 问题二: android.support.design.wid…...
Linux复习——基础知识
作者简介:一名云计算网络运维人员、每天分享网络与运维的技术与干货。 座右铭:低头赶路,敬事如仪 个人主页:网络豆的主页 1. 有关早期linux系统中 sysvin的init的7个级别描述正确的是( )[选择1项] A. init 1 关机状态 B. init 2 字符界面多用户模式 …...
【数据结构】实验三:链表
实验三链表 一、实验目的与要求 1)熟悉链表的类型定义; 2)熟悉链表的基本操作; 3)灵活应用链表解决具体应用问题。 二、实验内容 1)请设计一个单链表的存储结构,并实现单链表中基本运算算…...
第4集丨webpack 江湖 —— loader的安装和使用
目录 一、loader简介1.1 使用 loader1.1.1 配置文件方式1.1.2 内联方式 1.2 loader 特性1.3 解析 loader1.4 命名规范 二、css loader的安装和使用2.1 安装2.2 配置2.3 测试 三、 less-loader 的安装和使用3.1 安装3.2 配置3.3 测试3.4 附件3.4.1 webpack.config.js3.4.2 index…...
【Lua学习笔记】Lua进阶——协程
文章目录 协程协程的定义和调度StatusRunning 协程 协程是一种并发操作,相比于线程,线程在执行时往往是并行的,并且线程在创建销毁执行时极其消耗资源,并且过长的执行时间会造成主进程阻塞。而协程可以以并发时轮值时间片来执行&…...
亚马逊云科技纽约峰会,充分释放数据价值和生成式AI的潜力
生成式AI将深刻改变每个公司的运营方式,标志着人工智能技术发展的新转折点。亚马逊云科技昨日在纽约峰会上宣布,推出七项生成式AI新功能,进一步降低了生成式AI的使用门槛,让无论是业务用户还是开发者都能从中受益。借助这些新功能…...
什么是 web3?
在百度搜索引擎输入 “Web3”、“大厂”。跳出来基本都是这样的标题. 以及如今的互联网行业 “哀鸿遍野”,不仅内卷,还裁员。然后掀起一阵风,猛吹 Web3 的好,数据回归用户……最后再 “威逼利诱” 一下,Web3 就是 20 年…...
[驱动开发]字符设备驱动应用——点灯
点亮开发板stm32mp157的三盏灯 //头文件 #ifndef __LED_H__ #define __LED_H__//封装GPIO寄存器 typedef struct { volatile unsigned int MODER; // 0x00volatile unsigned int OTYPER; // 0x04volatile unsign…...
前端学习——Vue (Day5)
自定义指令 <template><div><h1>自定义指令</h1><input v-focus ref"inp" type"text" /></div> </template><script> export default {// mounted(){// this.$ref.inp.focus()// }// 2. 局部注册指令di…...
OpenClaw技能组合拳:GLM-4.7-Flash完成跨平台内容同步
OpenClaw技能组合拳:GLM-4.7-Flash完成跨平台内容同步 1. 为什么需要跨平台内容同步 上周我遇到一个典型的内容创作者困境:在知乎看到一篇优质技术文章,想把它保存到Notion知识库,同时转换成适合公众号发布的格式。传统做法需要…...
OpenClaw隐私保护设计:GLM-4.7-Flash本地处理医疗笔记整理
OpenClaw隐私保护设计:GLM-4.7-Flash本地处理医疗笔记整理 1. 为什么医疗数据必须留在本地? 去年帮家人整理慢性病就诊记录时,我遇到一个两难选择:要么手动整理上百张化验单和处方笺,要么使用云端OCR工具自动处理。当…...
OpenClaw数据可视化:GLM-4.7-Flash分析结果自动图表生成
OpenClaw数据可视化:GLM-4.7-Flash分析结果自动图表生成 1. 为什么需要自动化数据可视化 作为一名经常需要处理数据的开发者,我发现自己80%的时间都花在了数据清洗和图表调整上。每次分析新数据集时,都要重复这些步骤:写Python脚…...
【苍穹外卖 | 篇⑥】登录流程
在牛某网看见了牛肉哥的帖子之后,打算向牛肉大佬学习,故开始书写CSDN博客,通过博客的方式来巩固自身知识学习。因为之前有粗略的学习了Java Web 的基础课程,所以博客内容主要是巩固之前学习当中的模糊点,以及一些自己认…...
DDR5信号完整性解析:JESD79-5标准下的AC/DC输入测量关键指标
1. DDR5信号完整性的核心挑战 DDR5作为新一代内存标准,将数据传输速率推向了前所未有的高度。但随之而来的信号完整性问题,却让不少硬件工程师头疼不已。想象一下,当数据速率突破6400MT/s时,信号在传输线上就像是在走钢丝…...
【同态加密实战】从Paillier到BFV:算法原理与编码艺术深度解析
1. 同态加密:数据隐私保护的魔法钥匙 想象一下,你有一把能锁住数据的魔法钥匙——即使数据被锁在箱子里,别人依然可以对箱子里的数据进行计算,而无需打开箱子看到原始内容。这就是同态加密的神奇之处。作为密码学领域的"圣杯…...
告别混乱!YOLOv8检测结果自动归档:按日期+编号整理图片和标签(附完整Python脚本)
YOLOv8检测结果智能归档系统:打造高效可追溯的计算机视觉工作流 计算机视觉项目管理的痛点与解决方案 在计算机视觉项目的日常开发中,YOLOv8作为当前最先进的实时目标检测框架之一,被广泛应用于从安防监控到工业质检的各个领域。然而…...
星图平台OpenClaw镜像开发:百川2-13B量化模型预装环境揭秘
星图平台OpenClaw镜像开发:百川2-13B量化模型预装环境揭秘 1. 为什么选择百川2-13B量化版作为OpenClaw的默认模型 当我第一次在星图平台看到预装的百川2-13B量化版镜像时,内心是有些惊喜的。作为一个长期在本地折腾大模型部署的开发者,我深…...
别再傻傻下载Gurobi软件了!Anaconda虚拟环境里一条conda命令搞定学术版安装(Win11实测)
颠覆认知的Gurobi安装指南:一条conda命令解锁学术版完整功能 每次看到同行们花半小时下载几个GB的Gurobi安装包,我就忍不住想分享这个被多数人忽略的高效方案。作为在运筹优化领域深耕多年的研究者,我发现90%的学术用户根本不需要走传统安装…...
给硬件工程师的PCIe协议栈拆解:从FPGA IP核视角看三层协议如何协同工作
给硬件工程师的PCIe协议栈拆解:从FPGA IP核视角看三层协议如何协同工作 当你在Xilinx UltraScale或Intel Stratix 10 FPGA中集成PCIe硬核IP时,是否曾好奇过那个配置向导里勾选的"Enable Advanced Mode"究竟在底层做了什么?物理层的…...
