首先每次买卖一定是在某天 $k$ 以当时的最大收入买入，再到第 $i$ 天卖出，那么易得方程：
$$f_i = \max \{\frac{A_iRate_kf_k}{A_kRate_k + B_k} + \frac{B_if_k}{A_kRate_k + B_k}\}$$
再令
$$\left\{\begin{aligned} x_k = \frac{Rate_kf_k}{A_kRate_k + B_k} \\ y_k = \frac{f_k}{A_kRate_k + B_k}\end{aligned}\right.$$
则有
$$\begin{aligned} f_i &= \max \{A_ix_k + B_iy_k\} \\ y_k &= - \frac{A_i}{B_i}x_k + \frac{f_i}{B_i} \end{aligned}$$
那么现在需要找到一个点 $(x_k, y_k)$ 使得直线的截距最大
由于斜率和横坐标皆不满足单调性，可以用平衡树等维护，这里使用CDQ分治实现
实现过程如下：
Ⅰ 将数据按照斜率$\frac{A_i}{B_i}$降序排序
Ⅱ 将区间按照操作顺序分为左右两部分处理
Ⅲ 先处理左半部分，维护左半边凸包（注意，此时左半边已按照 $x$ 排序）
Ⅳ 处理左半边对右半边的影响，由于已按照斜率降序排序，所以普通斜率优化即可
Ⅴ 将区间按照 $x$ 排序
代码
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 1e05 + 10;
const double INF = 1e60;
const double eps = 1e-08;
int Dcmp (double p) {
if (fabs (p) < eps)
return 0;
return p < 0 ? - 1 : 1;
}
struct CashSt {
double a, b, rate;
double k, x, y;
int index;
CashSt () {}
bool operator < (const CashSt& p) const {
return Dcmp (x - p.x) == 0 ? Dcmp (y - p.y) < 0 : Dcmp (x - p.x) < 0;
}
} ;
CashSt Cash[MAXN];
bool comp (const CashSt& a, const CashSt& b) {
return Dcmp (a.k - b.k) > 0;
}
int N;
double slope (CashSt a, CashSt b) {
if (Dcmp (b.x - a.x) == 0)
return INF;
return (b.y - a.y) / (b.x - a.x);
}
double f[MAXN]= {0};
CashSt Que[MAXN];
int l = 1, r = 0;
CashSt temp[MAXN];
void CDQ (int left, int right) {
if (left == right) {
f[left] = max (f[left], f[left - 1]);
Cash[left].y = f[left] / (Cash[left].a * Cash[left].rate + Cash[left].b);
Cash[left].x = Cash[left].y * Cash[left].rate;
return ;
}
int mid = (left + right) >> 1;
int p1 = left - 1, p2 = mid;
for (int i = left; i <= right; i ++)
Cash[i].index <= mid ? temp[++ p1] = Cash[i] : temp[++ p2] = Cash[i];
for (int i = left; i <= right; i ++)
Cash[i] = temp[i];
CDQ (left, mid);
l = 1, r = 0;
for (int i = left; i <= mid; i ++) {
while (l < r && Dcmp (slope (Que[r - 1], Que[r]) - slope (Que[r], Cash[i])) < 0)
r --;
Que[++ r] = Cash[i];
}
for (int i = mid + 1; i <= right; i ++) {
while (l < r && Dcmp (slope (Que[l], Que[l + 1]) - Cash[i].k) > 0)
l ++;
f[Cash[i].index] = max (f[Cash[i].index], Cash[i].a * Que[l].x + Cash[i].b * Que[l].y);
}
CDQ (mid + 1, right);
l = left, r = mid + 1;
int p = 0;
while (l <= mid && r <= right) {
if (Cash[l] < Cash[r])
temp[++ p] = Cash[l], l ++;
else
temp[++ p] = Cash[r], r ++;
}
while (l <= mid)
temp[++ p] = Cash[l], l ++;
while (r <= right)
temp[++ p] = Cash[r], r ++;
for (int i = 1; i <= p; i ++)
Cash[i + left - 1] = temp[i];
}
double getnum () {
double num = 0.0;
char ch = getchar ();
double T = 1.0;
while (! isdigit (ch))
ch = getchar ();
while (isdigit (ch))
num = num * 10.0 + (ch - '0') * 1.0, ch = getchar ();
if (ch == '.') {
ch = getchar ();
while (isdigit (ch))
num = num + (T /= 10.0) * (ch - '0'), ch = getchar ();
}
return num;
}
int main () {
scanf ("%d%lf", & N, & f[0]);
for (int i = 1; i <= N; i ++) {
double a = getnum (), b = getnum (), rate = getnum ();
Cash[i].a = a, Cash[i].b = b, Cash[i].rate = rate;
Cash[i].index = i;
Cash[i].k = - a / b;
}
sort (Cash + 1, Cash + N + 1, comp);
CDQ (1, N);
printf ("%.3f\n", f[N]);
return 0;
}
|
