当前位置： 首页 > news >正文

P11290 【MX-S6-T2】「KDOI-11」飞船

news 2025/7/11 2:00:21

题目大意：有i种加油站，最开始速度为1，每次加油可以使速度*v，每次加油有一个时间代价，求到达终点所需最小时间。

思路：不妨考虑dp，贪心是错误的。

对于速度而言，y<=10^9，所以速度一定<10^9，所以速度是指数增长的，状态数不会很多。

于是只有两种状态2^j*3^k，设f[i][j][k]表示前i个加油站加到速度为2^j*3^k。

有两种转移策略：

1.f[i][j][k]=min(f[i-1][j][k]+(a[i].x-a[i-1].x)/1.0/(fac1[j]*fac2[k]),f[i][j][k]);

表示继承前一个点的值

2.f[i][j][k]=min(f[i-1][j-1][k]+a[i].t*1.0+(a[i].x-a[i-1].x)/1.0/(fac1[j-1]*fac2[k]),f[i][j][k]);

当且仅当vi=2

3.f[i][j][k]=min(f[i-1][j][k-1]+a[i].t*1.0+(a[i].x-a[i-1].x)/1.0/(fac1[j]*fac2[k-1]),f[i][j][k]);

当且仅当vi=3

4.vi=4同理

考虑计算答案，对于每一个终点而言，离它最近且不在它的位置上是最优的。因为这个点记录了前i个点的最优值

枚举每种状态即可，复杂度O(n*log_{2}^2(\alpha ))级别

http://www.lryc.cn/news/488767.html

相关文章：

  • WebGIS地图框架有哪些?
  • 量化加速知识点（整理中。。。）
  • BLIP-2模型的详解与思考
  • 2024年11月22日 十二生肖 今日运势
  • 小米C++ 面试题及参考答案上（120道面试题覆盖各种类型八股文）
  • SQL SELECT 语句：基础与进阶应用
  • 微服务即时通讯系统的实现（服务端）----（1）
  • 《Spring 依赖注入方式全解析》
  • 【C++动态规划】1411. 给 N x 3 网格图涂色的方案数|1844
  • 外包干了3年，技术退步明显...
  • SpringBoot 2.x 整合 Redis
  • React的API✅
  • 什么是全渠道客服中心？都包括哪些电商平台？
  • Jtti：如何知晓服务器的压力上限?具体的步骤和方法
  • 贪心算法（1）
  • SpringBoot，IOC，DI，分层解耦，统一响应
  • 目标驱动学习python动力
  • 力扣-Hot100-回溯【算法学习day.39】
  • 小熊派Nano接入华为云
  • 【linux硬件操作系统】计算机硬件常见硬件故障处理
  • 谈学生公寓安全用电系统的涉及方案
  • 自动语音识别（ASR）与文本转语音（TTS）技术的应用与发展
  • Go 语言数组
  • 13. 【.NET 8 实战--孢子记账--从单体到微服务】--简易权限--完善TODO标记的代码
  • 深入剖析Java内存管理：机制、优化与最佳实践
  • 【Amazon】亚马逊云科技Amazon DynamoDB 实践Amazon DynamoDB
  • Qt-常用的显示类控件
  • LabVIEW内燃机缸压采集与分析
  • 【Linux学习】【Ubuntu入门】1-7 ubuntu下磁盘管理
  • VScode clangd插件安装