[BZOJ1492/Luogu4027][NOI2007]货币兑换Cash(动态规划,斜率优化,CDQ分治)

发布于 2018-04-08  6 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1492/Luogu4027][NOI2007]货币兑换Cash(动态规划,斜率优化,CDQ分治)

Description

小 Y 最近在一家金券交易所工作。该金券交易所只发行交易两种金券:A 纪念券(以下简称 A 券)和 B 纪念券(以下简称 B 券)。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。
每天随着市场的起伏波动,两种金券都有自己当时的价值,即每一单位金券当天可以兑换的人民币数目。我们记录第 K 天中 A 券和 B 券的价值分别为 AKA_KAK​ 和BKB_KBK​ (元/单位金券)。
为了方便顾客,金券交易所提供了一种非常方便的交易方式:比例交易法。
比例交易法分为两个方面:
a) 卖出金券:顾客提供一个[0,100]内的实数 OP 作为卖出比例,其意义为:将 OP%的 A 券和 OP%的 B 券以当时的价值兑换为人民币;
b) 买入金券:顾客支付 IP 元人民币,交易所将会兑换给用户总价值为IP 的金券,并且,满足提供给顾客的 A 券和 B 券的比例在第 K 天恰好为 RateKRate_KRateK​ ;
例如,假定接下来 3 天内的 AkA_kAk​ 、BkB_kBk​ 、RateKRate_KRateK​ 的变化分别为:
时间 AkA_kAk​ BkB_kBk​ RatekRate_kRatek​
第一天 1 1 1
第二天 1 2 2
第三天 2 2 3
假定在第一天时,用户手中有 100 元人民币但是没有任何金券。
用户可以执行以下的操作:
时间 用户操作 人民币(元) A 券的数量 B 券的数量
开户 无 100 0 0
第一天 买入 100 元 0 50 50
第二天 卖出 50% 75 25 25
第二天 买入 60 元 15 55 40
第三天 卖出 100% 205 0 0
注意到,同一天内可以进行多次操作。
小 Y 是一个很有经济头脑的员工,通过较长时间的运作和行情测算,他已经知道了未来 N 天内的 A 券和 B 券的价值以及 Rate。他还希望能够计算出来,如果开始时拥有 S 元钱,那么 N 天后最多能够获得多少元钱。

Tag

动态规划,斜率优化,CDQ分治

解决思路

题目里面明确提示了必然存在一种最优的买卖方案满足:每次买进操作使用完所有的人民币;每次卖出操作卖出所有的金券。
所以不妨设F[i]表示前i天的最大收益(RMB),那么F[i]可以由之前的某一天j的钱全部换成金券再在这一天换回来。再设X[i]表示第i天的钱全部换成A券的数量和Y[i]表示第i天的钱全部换成B券的数量。
\[F[i]=X[i]*A[i]+Y[i]*B[i]\]
又因为\(\frac{X[i]}{Y[i]}=Rate[i]\),带入解得
\[X[i]=\frac{R[i]*F[i]}{A[i]*R[i]+B[i]} \quad Y[i]=\frac{F[i]}{A[i]*R[i]+B[i]}\]
所以转移方程为
\[F[i]=A[i]*X[j]+B[i]*Y[j]\]
化成斜率形式
\[Y[j]=-\frac{A[i]}{B[i]}*X[j]+\frac{F[i]}{B[i]}\]
由于要最大化截距,所以维护一个凸包。但是,这里不论是斜率还是x都不是递增的,那么有两种维护方式,一种就是splay维护,另一种是CDQ分治。这里使用CDQ分治的方法。
即,每一次分治左右半边,先求左边的答案,然后让左边按照x有序,右边按照斜率k有序。当然大前提一定是在要保证左边的id小于右边的id,这样才能用左边更新右边。那么维护一个左边的凸包,来利用斜率优化更新右边,用一个单调队列就好了。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1492/Luogu4027][NOI2007]货币兑换Cash(动态规划,斜率优化,CDQ分治)


HNCJ OIer 一枚