【双指针优化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…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
Ubuntu系统下交叉编译openssl
一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机:Ubuntu 20.04.6 LTSHost:ARM32位交叉编译器:arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...
