[关闭]
@zzzc18 2018-02-01T00:18:54.000000Z 字数 4190 阅读 566

BZOJ1492: [NOI2007]货币兑换Cash

动态规划-斜率优化 CDQ分治 bzoj


Description

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

Input

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

【提示】
1.输入文件可能很大,请采用快速的读入方式。
2.必然存在一种最优的买卖方案满足:
每次买进操作使用完所有的人民币;每次卖出操作卖出所有的金券。

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

Sample Input

3 100
1 1 1
1 2 2
2 2 3

Sample Output

225.000

HINT
dd(3).png-21.3kB


Solution

自然是少不了大佬的讲解啊
【陈丹琪】从《Cash》谈一类分治算法的应用.pdf314.1kB

首先题设比较复杂,不仔细读题,后面的方程肯定写不出来。

考虑到,如果有一天卖出会让你盈利,肯定是全部卖出时盈利更多。
同理,如果有一天买入会使得之后某一天卖出时赚得更大利润,那么这一天一定会全部买入。
没有上面两点这题根本不可做。

对于动归的状态,记作 分别表示第 天如果全部买入,可以最多获得 券,与此同时可以买到 券。 是最主要的状态。姑且把m看作质量吧,不知道该咋起名字

这样就有了 DP 方程(注意 别乱了):

这样得到的是一个 的算法,val的最大值为最终答案

考虑对于一个决策点 ,如果有两个决策方案 ,那么 优当且仅当:

这时,这已经很像斜率优化了,但是因为没有各种单调性,所以没法搞事。
我们直接令 使得其有一个单调性。

这就可以斜率优化了这是一个上凸壳

接下来,由于 实际上并不单调,所以需要用平衡树维护上凸包我没写这个
或者使用 CDQ分治

首先对于区间 ,可以通过 的信息做出来一个上凸包,用于更新 的决策,不一定是最终的最优,但要保证是 转移过来的最优情况。
考虑把 看做第一维, 看做第二维。
将第一维排序(升序降序都可以写出来),对第二维进行类似归并的过程。
具体过程是
按下标进行对每一天信息的划分(小于 划到 否则 。由于之前排过序,划分后仍然有序)

构建凸包。进行决策,由于和凸包都是单调的,可以算一下所有的最优解。

按照 升序排序,这是可以进行斜率优化的基础。

这样保证了斜率优化的可行性(单调递增),同时又可以不让决策的先后错乱(比如先在第三天操作再去第二天操作),是一个优秀的分治算法。时间复杂度

  1. /**************************************************************
  2. Problem: 1492
  3. User: zzzc18
  4. Language: C++
  5. Result: Accepted
  6. Time:1512 ms
  7. Memory:10592 kb
  8. ****************************************************************/
  9. #include<cmath>
  10. #include<cstdio>
  11. #include<cstring>
  12. #include<algorithm>
  13. using namespace std;
  14. const int MAXN = 100000+9;
  15. const double EPS = 1e-9;
  16. const double INF = 1e20;
  17. int n;
  18. double ans[MAXN];
  19. struct DATA{
  20. double A,B,rate;
  21. int id;
  22. }num[MAXN];
  23. bool DATAcmp(const DATA &X,const DATA &Y){
  24. return (-X.A/X.B)<(-Y.A/Y.B);
  25. }
  26. struct DP{
  27. double ma,mb;//表示A的数量以及B的数量
  28. }dp[MAXN];
  29. double K(int x,int y){
  30. if(dp[x].ma==dp[y].ma)return -INF;
  31. return (dp[x].mb-dp[y].mb)/(dp[x].ma-dp[y].ma);
  32. }
  33. bool jud(int x,int y){
  34. return dp[x].ma<dp[y].ma;
  35. }
  36. void CDQ(int l,int r){
  37. if(l==r){
  38. ans[l]=max(ans[l],ans[l-1]);
  39. dp[l].mb=ans[l]/(num[l].A*num[l].rate+num[l].B);
  40. dp[l].ma=dp[l].mb*num[l].rate;
  41. return;
  42. }
  43. static DATA tmp1[MAXN];
  44. static DP tmp2[MAXN];
  45. int mid=l+r>>1;
  46. int p1=l,p2=mid+1;
  47. for(int i=l;i<=r;i++){
  48. if(num[i].id<=mid)
  49. tmp1[p1++]=num[i];
  50. else
  51. tmp1[p2++]=num[i];
  52. }
  53. for(int i=l;i<=r;i++)
  54. num[i]=tmp1[i];
  55. CDQ(l,mid);
  56. static int top;
  57. static int sta[MAXN];
  58. top=1;
  59. for(int i=l;i<=mid;i++){
  60. while(top>2 && K(sta[top-1],sta[top-2])<K(sta[top-1],i))
  61. top--;
  62. sta[top++]=i;
  63. }
  64. int now=1;
  65. for(int i=r;i>mid;i--){
  66. while(now<top-1 && K(sta[now],sta[now+1])>=-num[i].A/num[i].B)
  67. now++;
  68. int t=num[i].id;
  69. ans[t]=max(ans[t],dp[sta[now]].ma*num[i].A+dp[sta[now]].mb*num[i].B);
  70. }
  71. CDQ(mid+1,r);
  72. p1=l,p2=mid+1;
  73. for(int i=l;i<=r;i++){
  74. if(p2>r || (p1<=mid && jud(p1,p2)))
  75. tmp2[i]=dp[p1++];
  76. else
  77. tmp2[i]=dp[p2++];
  78. }
  79. for(int i=l;i<=r;i++)
  80. dp[i]=tmp2[i];
  81. }
  82. void solve(){
  83. sort(num+1,num+n+1,DATAcmp);
  84. CDQ(1,n);
  85. printf("%.3lf\n",ans[n]);
  86. }
  87. int main(){
  88. scanf("%d",&n);
  89. scanf("%lf",&ans[0]);
  90. for(int i=1;i<=n;i++){
  91. scanf("%lf%lf%lf",&num[i].A,&num[i].B,&num[i].rate);
  92. num[i].id=i;
  93. }
  94. solve();
  95. return 0;
  96. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注