【问题描述】
小 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
}
