「BZOJ1492」[NOI2007] 货币兑换Cash

2014年6月18日6,87110

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论文即可。。。然后代码。。。

 

说点什么

提醒
avatar
QYP_2002
QYP_2002

黄学长,可以问下CDQ中最后那个sort是为什么吗???

我是神犇
我是神犇

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

我不是神犇
我不是神犇

好像都一样QAQ

SPACERE
SPACERE

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

cgt

I’m MaoDick

广大圆明

orz

hjz

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

hjz

催~更。。。。。

黑暗世界

233

hjz

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