$Noip2012\ Luogu1081$ 开车旅行 倍增优化$ DP$
2024-09-05 19:14:14
Description
Sol
1.发现对于每个城市,小A和小B的选择是固定的,可以预处理出来,分别记为ga[],gb[]
2.并且,只要知道了出发城市和出发天数,那么当前城市和小A,小B各行驶的路程也是一定的,同样可以分别预处理出来
具体怎么预处理:
1.其实就是"邻值查找"
简单讲一下,就是把所有城市的高度都存进set排好序,然后ga[i]一定是在set里与h[i]相邻的中最近的的,gb[i]是与h[i]相邻的中次近的
2.倍增优化:
1) 设$p[i][j][k]$表示从城市j出发,k第一个开车(k=0表示A,k=1表示B),已经行驶了2i天所到达的城市
$p[0][j][1]=ga[j],p[0][j][0]=gb[j] $
$i=1时,p[1][j][k]=p [0] [p[0][j][k]] [1-k]$
$i>1时,p[i][j][k]=p[i-1] [p[i-1][j][k]][k]$
2)设$a[i][j][k]$表示......小A行驶的路程
$a[0][j][0]=dis(j,ga[j]),a[0][j][1]=0$
$i=1时,a[1][j][k]=a[0][j][k]+a[0][p[0][j][k]][1-k]$
$i>1时,a[i][j][k]=a[i-1][j][k]+a[i-1][p[i-1][j][k]][k]$
3)设$b[i][j][k]$表示......小B....
和小A类似...
询问1:枚举出发城市,倒序枚举2的整数次幂保证总路程小于等于X
询问2:直接倒序枚举2的整数次幂保证总路程小于等于X即可
Code
太难写了咕咕咕$qwq$
最新文章
- Mysql两个引擎对比
- Subliem Text 3 的安装和使用
- javascript练习-子类调用父类的构造函数和方法
- 如何使用NPOI 导出到excel和导入excel到数据库
- Newtonsoft.Json学习笔记
- HDU 1494 跑跑卡丁车 (DP)
- bzoj1015:[JSOI2008]星球大战starwar
- 有关sort函数的用法
- JAVA面向对象-----接口的特点
- Java原型模式
- The application to execute does not exist: 'C:\Users\Administrator\.dotnet\tools\.store\dotnet-aspnet-codegenerator\2.2.0-rtm-35687\dotnet-aspnet-codegenerator\2.2.0-rtm-35687\tools\netcoreapp2.1\any\
- stringstream
- Js分支结构 switch--case
- 计算几何---凸包问题(Graham/Andrew Scan )
- python获取命令行参数 启动文件
- Hdu1163 Eddy's digitai Roots(九余数定理)
- 借助腾讯云CDN开启全站https及问题解决分享
- bzoj1617 / P2904 [USACO08MAR]跨河River Crossing
- thunk 函数
- DXEditingRow的错误原因
热门文章
- 5-2 正则表达式及其re模块
- 18-2 djanjo中间件和orm多对多操作,以及ajax
- 2019-8-31-dotnet-通过-WMI-拿到显卡信息
- HDFS概念名称节点和数据节点-基本模型
- HZOJ 辣鸡(ljh)
- H3C 路由器SSH服务配置命令(续)
- 非常优秀的Javascript(AJAX) 开发工具:Aptana
- Eclipse里编辑代码,进度条出现“Remote System Explorer Operation”解决方法
- redis 写入数据 越来越慢 是什么原因
- asp.net mvc获取路由参数