干物妹小埋 (离散化 + 线段树 + DP)
2024-09-02 22:00:54
链接:https://ac.nowcoder.com/acm/contest/992/B
来源:牛客网
题目描述
在之前很火的一个动漫《干物妹小埋》中,大家对小埋打游戏喝可乐的印象十分的深刻。
现在欧尼酱将小埋的快乐水全部分开藏在了家具的顶端。
小埋使出空中1080°转身接战术翻滚跳到任一家具上,她相信,只要她翻滚的足够快,欧尼酱就跟不上她。
1.为获取梦幻开局,小埋一套技能可以使她一开始掉落在任一家具上。
2.小埋家的家具按顺序给出,每个家具可跳可不跳,为避开欧尼酱的追击,小埋翻滚到某个家具上面后,只能向前继续翻滚。
3.启动超重力感应系统的小埋不会从较高的家具翻滚到较低的家具上。
4.由于每个家具上的快乐水都有对应的happy值,IQ==250的小埋会选择一条happy值总和最大的路线。
那么,最终小埋将获得的happy值总和是多少呢?
输入描述:
第一行一个整数n(0<n<=200000),表示小埋家的家具数。 第二行n个整数,对于每个整数ai, 0<=ai<=10^9,表示第i个家具的高度。 第三行n个整数,对于每个整数vi, 0<=vi<=10^9,表示第i个家具上的快乐水的happy值。
输出描述:
一个整数,表示小埋获得的happy值总和。
析:根据题意可以知道,对于跳到第 i 个位置的得到最高的方法就是从前面的某个小于等于它的高度的位置转移过来,也就是求 Max{dp[j]},其中 j 的高度是小于等于 i 的,这样的话,就可以对前面的所有小于等于高度 i 的所有位置求个最大值,使用离散化+线段树很容易就解决了,当然也可以使用树状数组,但我比较习惯使用线段树
最新文章
- Swiper – 经典的移动触摸滑块插件【免费】
- windows下的BT服务器搭建方案
- Clean Code(二):函数
- SRM 507(2-1000pt)
- 小白鼓捣GIT的心得
- 俄罗斯方块:Python实现
- linux下CDROM挂载
- Wikioi 1080一维树状数组
- Pattern | CLiPS
- 运用Detours库hook API(原理是改写函数的头5个字节)
- sysadmin_basement
- Nodejs 进阶:Express 常用中间件 body-parser 实现解析
- 从头开始学Maven【仓库】
- WARN [wxpay java sdk] - report fail. reason: report.mch.weixin.qq.com:80 failed to respond
- VS2013 中 CString类型转换为LPCSTR类型
- OkHttp3 任务队列
- 卸载Myeclipse10.5 报错“an error has occured.See the log file ...Uninstaller\...”
- 《MySQL必知必会》[07] 管理事务处理
- 第11月第8天 ffmpeg ffplay
- 九个问题从入门到熟悉HTTPS
热门文章
- linux中高级信号函数sigaction和sigqueue实例
- java中volatile关键字的作用
- jquery设置input不可编辑,背景变灰,鼠标变禁止
- 【转】Windows 7下用VMware Workstation 10虚拟机安装 Ubuntu 14.04
- System x 服务器制作ServerGuide U盘安装Windows Server 2008 操作系统 --不格式化盘
- 【LOJ】#3051. 「十二省联考 2019」皮配
- Spring4学习回顾之路12-事务
- 剑指offer43:左旋转字符串(字符串):对于一个给定的字符序列S,请你把其循环左移K位后的序列输出。
- MongoDB数据库、集合、文档的操作
- 数据结构和算法总结(三):A* 寻路算法