#P17979. Market
Market
Market
题目描述
你准备在接下来的 天内反复买卖同一套公寓。开始时没有公寓,并拥有 的资金。你在任何时刻至多拥有一套公寓。
第 天的公寓价格 是在实数区间 上均匀随机选取的数,其中 。不同天的价格独立选取。
通常,你在第 天开始时才知道当天的实际价格 ,随后决定是否交易:若没有公寓,可以以 买入;若拥有公寓,可以以 卖出;也可以不交易。
在第一天开始之前,你有一次提前获知信息的机会:先选定恰好 个日期,然后立即得知这些日期的实际价格。对于未选择的日期,仍然只能在当天开始时得知价格。选择日期集合时,你还不知道任何一天的实际价格。
第 天结束时,你必须没有公寓。利润定义为最终资金减去初始资金。
如果你最优地选择提前获知价格的日期,并根据已知信息最优地安排每天的交易,求利润的最大期望值。
输入格式
第一行两个整数 。
接下来 行,每行两个整数 ,描述第 天价格的均匀分布区间。
输出格式
输出一个实数,表示最大期望利润。
允许的相对或绝对误差为 。具体地,若正确答案为 ,输出为 ,则要求
小数点后最多可以输出 位数字。
数据范围
,,。
样例 1
输入
4 0
10 30
10 30
40 50
30 60
输出
28.75
样例 2
输入
4 1
10 30
10 30
40 50
30 60
输出
31.3888888889
样例 3
输入
6 3
10 50
30 70
50 70
30 50
30 40
10 40
输出
33.6805555556
样例说明
第一组不能提前获知任何一天的价格。一种最优策略是在第 或第 天买入,期望支出为 ,并在第 或第 天卖出,期望收入为 。
第二组最优选择是提前知道第 天的价格,答案为 。第三组可以最优地选择日期集合 。