题解：
这题非常容易想到一个错误的贪心
就是按照ai排序 然后尽量取ai小的
但是有很明显的问题就是如果取了小的ai
那会导致那些原本可能存在这些ai就可以去掉的大的人因此不能取了
而有可能可以先去取他们再来取它（当它的b值很大时）
这道题的正解和noip那道国王挺像的
既然按照ai贪心不行
根据上面的分析，比较显然是按照ai+bi来贪心
也就是说我们要保证取得顺序是ai+bi递增的
考虑交换两项来证明这个东西
如果先取后面然后可以再取前面 但是现在先取前面再取后面是不行的
这个贪心就会被推翻
我们可以把它转化成方程
sum+b2>=k
sum-a2+b1>=k
sum-a1+b2<k
a1+a2<b1+b2
很显然234这三个式子是矛盾的
所以贪心是成立的
然后是比较简单的
注意到人数比sum的取值范围小
所以我们定义f[i]表示逃跑i个人剩余ai的最大值
复杂度n^2
【bzoj3174】[Tjoi2013]拯救小矮人的更多相关文章
-
BZOJ3174 Tjoi2013 拯救小矮人（贪心+DP）
传送门 Description 一群小矮人掉进了一个很深的陷阱里,由于太矮爬不上来,于是他们决定搭一个人梯.即:一个小矮人站在另一小矮人的 肩膀上,知道最顶端的小矮人伸直胳膊可以碰到陷阱口.对于每一个 ...
-
bzoj3174 [Tjoi2013]拯救小矮人
Description 一群小矮人掉进了一个很深的陷阱里,由于太矮爬不上来,于是他们决定搭一个人梯.即:一个小矮人站在另一小矮人的 肩膀上,知道最顶端的小矮人伸直胳膊可以碰到陷阱口.对于每一个小矮人, ...
-
BZOJ3174:[TJOI2013]拯救小矮人(DP)
Description 一群小矮人掉进了一个很深的陷阱里,由于太矮爬不上来,于是他们决定搭一个人梯.即:一个小矮人站在另一小矮人的 肩膀上,知道最顶端的小矮人伸直胳膊可以碰到陷阱口.对于每一个小矮人, ...
-
BZOJ3174. [TJOI2013]拯救小矮人（dp）
题目链接 https://www.lydsy.com/JudgeOnline/problem.php?id=3174 题解 其实此题并不需要那么多YY的部分. 我们考虑若干个小矮人逃出的顺序.若跳出的 ...
-
BZOJ3174 TJOI2013 拯救小矮人 贪心、DP
传送门 原问题等价于:先给\(n\)个人排好顺序.叠在一起,然后从顶往底能走即走,问最多能走多少人 注意到一个问题:如果存在两个人\(i,j\)满足\(a_i + b_i < a_j + b_j ...
-
bzoj千题计划208：bzoj3174: [Tjoi2013]拯救小矮人
http://www.lydsy.com/JudgeOnline/problem.php?id=3174 按a+b从小到大排序,a+b小的在上面,先考虑让它逃出去 正确性不会证 感性理解一下,最后一个 ...
-
【BZOJ3174】[TJOI2013]拯救小矮人（贪心，动态规划）
[BZOJ3174][TJOI2013]拯救小矮人(贪心,动态规划) 题面 BZOJ 洛谷 题解 我们定义一个小矮人的\(A_i+B_i\)为它的逃跑能力. 我们发现,如果有两个小矮人\(x,y\), ...
-
【BZOJ-3174】拯救小矮人 贪心 + DP
3174: [Tjoi2013]拯救小矮人 Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 686 Solved: 357[Submit][Status ...
-
BZOJ_3174_[Tjoi2013]拯救小矮人_贪心+DP
BZOJ_3174_[Tjoi2013]拯救小矮人_贪心+DP Description 一群小矮人掉进了一个很深的陷阱里,由于太矮爬不上来,于是他们决定搭一个人梯.即:一个小矮人站在另一小矮人的 肩膀 ...
-
贪心+DP【洛谷P4823】 [TJOI2013]拯救小矮人
P4823 [TJOI2013]拯救小矮人 题目描述 一群小矮人掉进了一个很深的陷阱里,由于太矮爬不上来,于是他们决定搭一个人梯.即:一个小矮人站在另一小矮人的 肩膀上,知道最顶端的小矮人伸直胳膊可以 ...
随机推荐
-
Photon服务器进阶&;一个新游戏的出产（三）
下面或许该介绍介绍我用Photon写的一个4人联机麻将了~ 上图
-
使用decode函数实现统计
从上个星期起就在开始做统计图,各种统计图,昨天做的统计效果图如下: 在这里要根据工作平台和机构做统计,其中当字段A等于某个值时需要统计起来,也就是说假设等于2时需要做统计,字段 ...
-
item2，实现singleton模式
单例模式? 只能实现一个实例的类成为单例. ============== muduo库中单例模式实现 #include<boost/noncopyable.hpp> //#include ...
-
BZOJ 1610: [Usaco2008 Feb]Line连线游戏
1610: [Usaco2008 Feb]Line连线游戏 Description Farmer John最近发明了一个游戏,来考验自命不凡的贝茜.游戏开始的时 候,FJ会给贝茜一块画着N (2 &l ...
-
SAP HANA 能做什么
HANA不是一个数据仓库,而是一个平台,在这个平台之上用户可以构建数据仓库或集市.报表和仪表盘等. HANA能做的,首先是作为内存数据库,提供数据插入.修改和高效的查询功能. 其次,作为一个平台,在H ...
-
下载android4.4.2源码全过程（附已下载的源码）
今天在下载andriod源码,特来与大家分享一下我的经验.当然,网上教下载源码的教程较多,本文主要针对在GFW下下载源码出现的各种问题的解决方法. 1.首先安装下载客户端git , curl. 命令如 ...
-
PL/SQL 设置
1.如何批量导出建表语句? 通过菜单选择[Tools]–>[Export User Objects...],在打开的窗口中选择准备导出的表即可. 通过此种方式导出的sql脚本中不会有ins ...
-
通过cmd 使用 InstallUtil.exe 命令 操作 windows服务 Windows Service
要安装windows service 首先要找到 InstallUtil.exe,InstallUtil.exe位置在 C:\Windows\Microsoft.NET\Framework\v4.0. ...
-
kettle 合并记录步骤中的 关键字段和 比较字段的说明
该步骤用于将两个不同来源的数据合并,这两个来源的数据分别为旧数据和新数据,该步骤将旧数据和新数据按照指定的关键字匹配.比较.合并. 需要设置的参数: 旧数据来源:旧数据来源的步骤 新数据来源.新数据来 ...
-
Strusts2笔记6--拦截器
拦截器: Struts2的大多数核心功能都是通过拦截器实现的.拦截器之所以称之为“拦截器”,是因为它可以在执行Action之前或之后拦截下用户请求,执行一些操作,以增强Action方法的功能. Str ...