时间戳

首页 > 技术文章 > NOI2007 货币兑换

NOI2007 货币兑换

Blacko 2013-11-29 11:38 原文

【问题描述】

  小 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的变化分别为：

时间 Ak Bk Ratek
第一天 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天后最多能够获得多少元钱。

【输入格式】

第一行两个正整数N、S，分别表示小Y能预知的天数以及初始时拥有的钱数。接下来N行，第K行三个实数AK、BK、RateK，意义如题目中所述。

【输出格式】

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

-----------------------------------------------------------

正解=动归+平衡树

考虑简单Dp

　 　状态：设f[i]为第i天能赚的最多钱为多少

　　 方程：f[i]=max(f[i-1],na*A+nb*B)(j< i)

　　　　(na,nb为第j天能换到的A劵数量和B劵数量)

考虑优化：

　　设 na 为 x，nb 为 y

　　则sum=x*A+y*B 既 y = -A/B*x+sum/B

　　由于A，B为定值

　　　sum的Max以 -A/B 为斜率的过点(x,y)的截距的Max*B

　　显然可能得到Max解截距的点必然是个上凸壳

　　　　建立以x为关键字的平衡树维护值（其实很简(dan)单(teng)）

      由于在树上的点映射的截距具有单调性，

　　找最大值是便可通过平衡树的前驱后继判断Max在左子树或右子树；

代码如下：

　　

  1 #include<cstring>
  2 #include<algorithm>
  3 #include<cstdio>
  4 #include<string>
  5 #include<iostream>
  6 #include<queue>
  7 #define INF 99999999
  8 #define LL long long
  9 #define Cint(o) const int o=0
 10 #define Cdou(o) const double o=0
 11 #define Min(num1,num2) if(num1>num2) num1=num2
 12 #define Max(num1,num2) if(num1<num2) num1=num2
 13 struct Tree{
 14     int l,r,f;
 15     double x,y;
 16     Tree(Cint(a1),Cint(a2),Cint(a3),Cdou(a4),Cdou(a5)):
 17         l(a1),r(a2),f(a3),x(a4),y(a5){}
 18 }a[100010];
 19 int Root,Total,n;
 20 const long double O=1e-8;
 21 void cal(double sum,double A,double B,double K,double &na,double &nb){
 22     nb=sum/(A*K+B);
 23     na=nb*K;
 24 }
 25 void rig(int now){
 26     int f=a[now].f;
 27     a[now].f=a[f].f;
 28     if(a[a[f].f].l==f) a[a[f].f].l=now;
 29     if(a[a[f].f].r==f) a[a[f].f].r=now;
 30     a[f].f=now;
 31     a[f].l=a[now].r;
 32     a[a[now].r].f=f;
 33     a[now].r=f;
 34 }
 35     
 36 void lef(int now){
 37     int f=a[now].f;
 38     a[now].f=a[f].f;
 39     if(a[a[f].f].l==f) a[a[f].f].l=now;
 40     if(a[a[f].f].r==f) a[a[f].f].r=now;
 41     a[f].f=now;
 42     a[f].r=a[now].l;
 43     a[a[now].l].f=f;
 44     a[now].l=f;
 45 }
 46 double cross(Tree A,Tree B,Tree C){
 47     return (B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
 48             // x1 *y2-x2*y1
 49 }    
 50 void splay(int now,int F=0){
 51     while(a[now].f!=F){
 52         int f=a[now].f,ff=a[f].f;
 53         if(ff==F)
 54             if(a[f].l==now) rig(now);
 55             else lef(now);
 56         else
 57             if(a[ff].l==f)
 58                 if(a[f].l==now) rig(f),rig(now);
 59                 else lef(now),rig(now);
 60             else
 61                 if(a[f].l==now) rig(now),lef(now);
 62                 else lef(f),lef(now);
 63     }
 64     if(!F) Root=now;
 65 }
 66 
 67 void creat(){
 68     Total=2;
 69     Root=1;
 70     a[1].r=2;
 71     a[2].f=1;
 72     a[1].x=-INF;
 73     a[2].x=INF;
 74 }
 75 int prev(int now){
 76     splay(now);
 77     now=a[now].l;
 78     while(a[now].r) now=a[now].r;
 79     return now;
 80 }
 81 int succ(int now){
 82     splay(now);
 83     now=a[now].r;
 84     while(a[now].l) now=a[now].l;
 85     return now;
 86 }
 87 void del(int start,int now,int end){
 88     splay(start);
 89     splay(end,start);
 90     a[a[Root].r].l=0;
 91     //printf("Delte(%d)",now);
 92 }
 93 void maintain(int now){
 94     int p=prev(now),s=succ(now);
 95     if(p!=1&&s!=2)
 96         if(cross(a[p],a[s],a[now])<O){
 97             del(p,now,s);
 98             return ;
 99         }
100     while(1){
101         if(p==1) break;
102         int pp=prev(p);
103         if(pp!=1&&cross(a[pp],a[now],a[p])<O)
104             del(pp,p,now),
105             p=pp;
106         else 
107             break;
108     }
109     while(1){
110         if(s==2) break;
111         int ss=succ(s);
112         if(ss!=2&&cross(a[now],a[ss],a[s])<O)
113             del(now,s,ss),
114             s=ss;
115         else 
116             break;
117     }
118 }
119 void insert(double x,double y){
120     for(int now=Root;;){
121         if(a[now].x-x<O&&x-a[now].x<O){
122             Max(a[now].y,y);
123             maintain(now);
124             return ;
125         }
126         if(a[now].x-x>O)
127             if(a[now].l)
128                 now=a[now].l;
129             else {
130                 a[now].l=++Total;
131                 a[Total].f=now;
132                 a[Total].x=x;
133                 a[Total].y=y;
134                 maintain(Total);
135                 return ;
136             }
137         else 
138             if(a[now].r)
139                 now=a[now].r;
140             else{
141                 a[now].r=++Total;
142                 a[Total].f=now;
143                 a[Total].x=x;
144                 a[Total].y=y;
145                 maintain(Total);
146                 return ;    
147                 
148             }    
149     }
150 }
151 double fo(Tree now,double K){
152     return now.y-now.x*K;
153 }
154 int pre(int now){
155     //splay(now);
156     now=a[now].l;
157     while(a[now].r) now=a[now].r;
158     return now;
159 }
160 
161 int suc(int now){
162 //    splay(now);
163     now=a[now].r;
164     while(a[now].l) now=a[now].l;
165     return now;
166 }
167 double slove(double K){
168     for(int now=Root;;){
169         if(now==1){
170             now=suc(now);
171             continue ;
172         }
173         if(now==2){
174             now=pre(now);
175             continue ;
176         }
177         
178         if(a[now].l){
179             int k=pre(now);
180             if(k!=1&&fo(a[now],K)<fo(a[k],K)+O){
181                 now=a[now].l;
182                 continue ;
183             }
184         } 
185         if(a[now].r){
186             int k=suc(now);
187             if(k!=2&&fo(a[now],K)<fo(a[k],K)+O){
188                 now=a[now].r;
189                 continue ;
190             }
191         }
192         return fo(a[now],K);
193         
194     }
195 } 
196 int main(){
197     double A,B,K,na,nb,s;
198     scanf("%d%lf",&n,&s);
199     scanf("%lf%lf%lf",&A,&B,&K);
200     creat();
201     cal(s,A,B,K,na,nb);
202     insert(na,nb);
203     for(int i=1;i<n;i++){
204         scanf("%lf%lf%lf",&A,&B,&K);
205         double temp=slove(-A/B)*B;
206         Max(s,temp);
207         cal(s,A,B,K,na,nb);
208         insert(na,nb);
209     }
210     printf("%.3lf",s);
211 }
View Code

 

推荐阅读