【問題描述】
??小 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
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
