【bzoj1492】 [NOI2007]货币兑换Cash

2014年6月18日4,4569

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;

题解

此题见cdq论文

首先n^2的dp很好做

额然后是cdq分治

理论不是很难但是没写过还是比较蛋疼

理论就看cdq论文即可。。。然后代码。。。

 

  • hjz2014年6月19日 上午9:43 回复

    ORZ!!!求HZWER学长教我CDQ分治

    #1  
  • hjz2014年6月19日 上午9:49 回复

    催~更。。。。。

    #2  
  • hjz2014年6月20日 上午11:13 回复

    46行貌似应该叫“维护凸线”吧。。。

    #3  
  • 广大圆明2015年12月20日 上午10:57 回复

    orz

    #4  
  • cgt2015年12月20日 下午9:10 回复

    I’m MaoDick

    #5  
  • SPACERE2016年1月14日 下午3:40 回复

    黄学长那个分治过不了编译,暴力好像也是不对的

    #6  
  • 我是神犇2016年2月18日 下午5:03 回复

    黄学长第43行写错了>_<

    #7  
    • 我不是神犇2016年2月18日 下午5:38 回复

      好像都一样QAQ

      #71