[NOI2007]货币兑换Cash

[NOI2007]货币兑换Cash

Time Limit:5000MS  Memory Limit:65536K
Total Submit:84 Accepted:36
Case Time Limit:1000MS

Description

Input

第一行两个正整数N、S,分别表示小Y 能预知的天数以及初始时拥有的钱数。
接下来N 行,第K 行三个实数AK、BK、RateK,意义如题目中所述

Output

只有一个实数MaxProfit,表示第N 天的操作结束时能够获得的最大的金钱
数目。答案保留3 位小数。

Sample Input

3 100
1 1 1
1 2 2
2 2 3

Sample Output

225.000

Hint

测试数据设计使得精度误差不会超过10-7。
对于40%的测试数据,满足N ≤ 10;
对于60%的测试数据,满足N ≤ 1 000;
对于100%的测试数据,满足N ≤ 100 000;

Source

我又使用随机化算法强行AC了这道题目囧。。。。
WA+TLE N次。。。累成SB囧。。。
首先转化成维护凸壳大家都知道。。
我的办法基本上就是维护一个链表的数组。。
然后根据算法导论说的可以在Sqrt(N)的时间内在这个数组里面找一个元素。。
所以插入跟维护都可以做到Sqrt(N)。。。
然后硬做。。
就A掉了囧。。。
Code:
http://www.ideone.com/8hGL1

4 thoughts on “[NOI2007]货币兑换Cash

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>