【题解】loj#2353 [NOI2007]货币兑换

某CDQ好题.

没人看出上面这句话是有俩含义吗

小Y最近在一家金券交易所工作。该金券交易所只发行交易两种金券:$A$ 纪念券(以下简称 $A$ 券)和 $B$ 纪念券(以下简称 $B$ 券)。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。

每天随着市场的起伏波动,两种金券都有自己当时的价值,即每一单位金券当天可以兑换的人民币数目。我们记录第 $K$ 天中 $A$ 券和 $B$ 券的价值分别为 $A_K$ 和 $B_K$ (元/单位金券)。

为了方便顾客,金券交易所提供了一种非常方便的交易方式:比例交易法。

比例交易法分为两个方面:

a) 卖出金券:顾客提供一个 $[0,100]$ 内的实数 $\rm OP$ 作为卖出比例,其意义为:将 $\rm OP\%$ 的 $A$ 券和 $\rm OP\%$ 的 $B$ 券以当时的价值兑换为人民币;

b) 买入金券:顾客支付 $\rm IP$ 元人民币,交易所将会兑换给用户总价值为 $\rm IP$ 的金券,并且,满足提供给顾客的 $A$ 券和 $B$ 券的比例在第 $K$ 天恰好为 $\rm Rate_K$ ;

小 Y 是一个很有经济头脑的员工,通过较长时间的运作和行情测算,他已经知道了未来 $\rm N$ 天内的 $A$ 券和 $B$ 券的价值以及 $\rm Rate$。他还希望能够计算出来,如果开始时拥有 $\rm S$ 元钱,那么 $\rm N$ 天后最多能够获得多少元钱。

其中 $\rm N\leq 10^5$.

首先想到 $dp$ 。这个地方设计的 $dp$ 个人感觉还是比较 $\rm tricky$ 的。发现本质上最大化 $A$ 券或者 $B$ 券的数量和最大化手里拿到的rmb都是某些最优决策,所以不能一起维护。

发现通过券来维护rmb比较方便,于是考虑设 $f_i$ 表示在第 $i$ 天把rmb都花完能得到多少 $A$ 券。初值显然是

那么考虑如何以此计算rmb。发现第 $i$ 天可能会保有 $1\sim i-1$ 天时的金券。于是令 $g_i$ 表示前 $i$ 天的最大获利,发现可以这么转移:

转移的正确性在于,卖出的 $A$ 券和 $B$ 券的百分比必须一致,所以不会出现分多次卖的情况。于是喜提一个 $n^2$ 算法。

考虑优化。发现如果对于一个 $i$ 其转移点为 $j$,那么会有:

发现可以令 $y_i=\frac{f_i}{\mathrm{Rate_i}},x_i=f_i$ 。那么这就是一个斜率优化的标准形式。

但问题在于,$f_j$ 很悲惨的由于每天的兑换量有不同,它并不单增,并且斜率也不单增,所以不能用删除末尾几个(即单调队列)来维护凸壳,必须要用某些神秘 $\rm splay$ 技巧来加速这个过程。

然而还有另一种 $\rm CDQ$ 写法。大概就是考虑为了保证横坐标是单调的,所以要排序,但是排序之后转移就会失秩,而这个过程显然可以 $\rm CDQ$ 来优化,于是就没了。

值得注意的是,朴素的 $\rm CDQ$ 由于不需要严格按秩,即二进制拆分顺序不限,所以可以瞎分治。但是维护 $dp$ 的时候由于转移顺序必须按秩,所以有严格的分治顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

using namespace std ;
struct Cash{
double x, y, k ;
double A, B, R ; int ID ;
}T[MAXN], Div[MAXN] ;
int N ; double M ; double dp[MAXN] ;

namespace DP{
double Ans, t ;
inline void Solve1(){
Ans = M, dp[1] = M * T[1].R / (T[1].A * T[1].R + T[1].B) ;
for (int i = 1 ; i <= N ; ++ i){
for (int j = 1 ; j < i ; ++ j)
Ans = max(Ans, dp[j] * T[i].A + dp[j] / T[j].R * T[i].B) ;
dp[i] = Ans * T[i].R / (T[i].A * T[i].R + T[i].B) ;
}
printf("%.3lf\n", Ans) ;
}
}
namespace CDQ{
int stk[MAXN] ; const double INF = 1e9, eps = 1e-6;
inline bool Compare(const Cash & A, const Cash & B){ return A.k < B.k ;}
inline double getr(int d, int b){
if (fabs(T[d].x - T[b].x) <= eps) return INF ;
return (T[d].y - T[b]. y) / (T[d].x - T[b].x) ;
}
inline void Merge_sort(int L, int R, int Mid){
int l = L, r = Mid + 1 ;
for (int i = L ; i <= R ; ++ i)
if (l <= Mid && (r > R || T[l].x < T[r].x))
Div[i] = T[l ++]; else Div[i] = T[r ++] ;
for (int i = L ; i <= R ; ++ i) T[i] = Div[i] ;
}
void dp_CDQ(int L, int R){
if (L == R){
dp[L] = max(dp[L], dp[L - 1]) ;//?
T[L].y = dp[L] / (T[L].A * T[L].R + T[L].B), T[L].x = T[L].y * T[L].R ;
return ; //y : f[j] / Rate[j], x : f[j]。此处应该以f[j]单增来排序
}
int Mid = (L + R) >> 1, l = L - 1, r = Mid ; int top = 0 ;
for (rr int i = L ; i <= R ; ++ i)
if (T[i].ID <= Mid) Div[++ l] = T[i] ; else Div[++ r] = T[i] ;
for (rr int i = L ; i <= R ; ++ i) T[i] = Div[i] ; dp_CDQ(L, Mid) ; // 2
for (rr int i = L ; i <= Mid ; ++ i){
while (top > 1 && getr(stk[top], stk[top - 1]) < getr(stk[top], i)) -- top ;
stk[++ top] = i ;
}
for (rr int i = Mid + 1 ; i <= R ; ++ i){
while (top > 1 && getr(stk[top], stk[top - 1]) <= T[i].k) -- top ;
dp[T[i].ID] = max(dp[T[i].ID], T[stk[top]].x * T[i].A + T[stk[top]].y * T[i].B) ;
}
dp_CDQ(Mid + 1, R), Merge_sort(L, R, Mid) ;
}
inline void Solve2(){
dp[0] = M ;
sort(T + 1, T + N + 1, Compare) ;
dp_CDQ(1, N) ; printf("%.3lf\n", dp[N]) ;
}
}
int main(){
// freopen("1492.in", "r", stdin) ;
// freopen("1492.out", "w", stdout) ;
cin >> N >> M ;
for (int i = 1 ; i <= N ; ++ i)
scanf("%lf%lf%lf", &T[i].A, &T[i].B, &T[i].R),
T[i].k = -T[i].A / T[i].B, T[i].ID = i ;
if (N <= 5000) DP :: Solve1() ;
else CDQ :: Solve2() ; return 0 ;
}