BZOJ1492 [NOI2007] 货币兑换

Description

你有 \(S\) 元钱。在第 \(i\) 天你可以把 \(x\) 元钱变成 \(\frac{Rate_ix}{Rate_iA_i+B_i}\) 单位 A 金券和 \(\frac{x}{Rate_iA_i+B_i}\) 单位 B 金券;或把 \(a\) 单位 A 金券 \(b\) 单位 B 金券变成 \(A_ia+B_ib\) 元钱。

\(n\) 天后你最多能持有多少元钱。 \(n\leqslant10^6\)

Solution

显然我每次要么把现金全换成金券要么把金券全换成现金。

考虑 DP 。\(f_i\) 表示第 \(i\) 天结束时至多持有多少现金。

\(\begin{cases}x_i=Rate_iy_i\\y_i=\frac{f_i}{Rate_iA_i+B_i}\end{cases}\) 表示我在这一天把现金换成金券时至多持有的 A/B 券数,那么有

\[f_i = \max\left(f_{i-1}, \max_{j=0}^{i-1}(A_ix_j+B_iy_j)\right)\]

这是一个显然的斜率优化式子( \(A_ix_j+B_iy_j\) 可以看做 \(B_i\) 乘以“经过 \((x_i,y_i)\) 这个点的斜率为 \(-\frac{A_i}{B_i}\) 的直线的斜率”)。可以单调队列

似乎不大对…因为 \(x_i\)\(y_i\) 都不是递增的,没法单调队列维护凸包。平衡树维护凸包啊

考虑 CDQ 分治。具体的讲,首先我递归求出左边一半 \(f\) ,然后把左边一半里的 \((x_i, y_i)\) 按横坐标排序,右边一半按斜率排序;然后 \(O(n)\) 处理左边对右边的影响;然后递归求右边一半 \(f\) 即可。

复杂度 \(T(n)=2T(n/2)+O(n)\) ,可以解出 \(T(n)=O(n\log n)\)

Code

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
#include <algorithm>
#include <cctype>
#include <cstdio>

const int N = 1000050;
const double eps = 1e-6;

int n;
double f[N];
struct Point{
double Rate, A, B;
double x, y, k;
int id;
inline friend bool operator<(const Point &a, const Point &b) {
return a.k > b.k;
}
}P[N];

inline double abs(double x) { return x < 0 ? -x : x; }

inline double CP(const Point &a, const Point &b, const Point &c) {
// (b - a) x (c - a)
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

inline double calc(const Point &a, const Point &b) {
return a.x * b.A + a.y * b.B;
}

inline bool cmp(const Point &a, const Point &b) {
if (abs(a.x - b.x) <= eps) return a.y < b.y;
return a.x < b.x;
}

void Solve(int l, int r) { // [l, r)
if (r - l <= 1) {
if (l != 0) f[l] = std::max(f[l], f[l - 1]);
P[l].y = f[l] / (P[l].Rate * P[l].A + P[l].B);
P[l].x = P[l].y * P[l].Rate;
return;
}

int mid = (l + r) >> 1;
static Point _tmp[N], CV[N];
Point *tl = _tmp, *tr = _tmp + (mid - l);
for (int i = l; i < r; ++i) *((P[i].id < mid ? tl : tr)++) = P[i];
tl = _tmp;
for (int i = l; i < r; ++i) P[i] = *(tl++);

Solve(l, mid);

int m = 0;
for (int i = l; i < mid; ++i)
if (i == l || abs(P[i].x - P[i - 1].x) > eps) {
while (m > 1 && CP(CV[m - 2], CV[m - 1], P[i]) > 0) --m;
CV[m++] = P[i];
}
for (int i = mid, j = 0; i < r; ++i) {
while (j < m - 1 && calc(CV[j + 1], P[i]) > calc(CV[j], P[i])) ++j;
f[P[i].id] = std::max(f[P[i].id], calc(CV[j], P[i]));
}

Solve(mid, r);

tl = P + l, tr = P + mid;
Point *res = _tmp;
while (tl < P + mid || tr < P + r)
if (tr == P + r || (tl != P + mid && cmp(*tl, *tr)))
*(res++) = *(tl++);
else
*(res++) = *(tr++);
for (tl = P + l, res = _tmp; tl != P + r; ++tl)
*tl = *(res++);
}

int main() {
scanf("%d%lf", &n, &f[0]);
for (int i = 0; i < n; ++i) {
scanf("%lf%lf%lf", &P[i].A, &P[i].B, &P[i].Rate);
P[i].k = -P[i].A / P[i].B;
P[i].id = i;
}

std::sort(P, P + n);
Solve(0, n);
printf("%.3lf\n", f[n - 1]);

return 0;
}