[NOI 2007] 货币兑换

题目大意

有 A、B 两种券,券的数目可以是一个实数。第 $K$ 日时,两种券的单价分别为 $A_K$、$B_K$(实数),交易比例为 $rate_K$。每日,你可以选择买入一定量的券,且 A 券数目与 B 券数目之比必须为 $rate_K$;或卖出已有券的 $OP\%$,即所持 A 券的 $OP\%$ 和所持 B 券的 $OP\%$ 。同一日内可进行多次操作,也可以不操作。已知 $n$ 日内的单价与交易比例,初始时有 $S$ 的钱,但没有任何券,求 $n$ 日后的最大收益。

提示:必然存在一种最优的买卖方案满足:每次买进操作使用完所有的人民币;每次卖出操作卖出所有的金券。

$1 \leq n \leq 10^6$

$0 < A_K, B_K \leq 10$

$0 < rate_K \leq 100$

题目链接

LibreOJ 2353(有 spj)

BZOJ 1492(无 spj,保留三位小数)

题解

由提示可写出以下 DP 方程:

表示在第 $i$ 日卖出全部券的最大收益,$x(i)$、$y(i)$ 表示第 $i$ 日用最大收益买到的两种券的数目,他们满足:

则答案为 $\max_\limits{1 \leq i \leq n}f(i)$ 。

$f(i) = A_i \times x(j) + B_i \times y(i)$ 可写作 $y(i) = -\frac{A_i}{B_i} x(j)+ \frac{f(i)}{B_i}$,对于确定的 $i$,以 $x(j)$ 为横坐标、$y(j)$ 为纵坐标,可视作一族平行的直线,转移即要求截距最大,于是可能的决策点必在一上凸壳上。

由于 $x(i)$ 和 $y(i)$ 不具单调性,只能动态维护上凸壳,用 Splay 维护之即可。

本题亦可用 CDQ 分治解决:

考虑可用单调队列做到 $O(n)$ 的斜率优化 DP 的题,它们满足:

  • 插入线性:横坐标单调不减
  • 查询线性:目标斜率单调不减
  • 默认:下标顺序

于是可以考虑用 CDQ 分治解决这三个约束,大致思路是:

用左侧更新右侧答案,然后归并。左侧需要维护凸壳,要满足插入线性;左侧的下标应小于右侧的下标;右侧更新答案,要满足查询线性。于是可以考虑先整体满足查询线性,然后按下标分为两侧,先计算左侧,然后左侧更新右侧,之后计算右侧,最后归并为插入线性。

相比之下,Splay 的代码虽然更长,但内存更少、常数更小,而且思维上简单粗暴。

代码

Splay 维护动态凸壳

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <cstdio>
#include <algorithm>

const int MAXN = 1000005;
const double EPS = 1e-9;

int dcmp(double a, double b = 0) {
double d = a - b;
return std::abs(d) <= EPS ? 0 : (d > 0 ? 1 : -1);
}

struct Splay {
struct Node {
Node *c[2], *fa, *pred, *succ;
double x, y;

Node() {}
Node(Node *fa, double x, double y) : x(x), y(y), c(), fa(fa), pred(NULL), succ(NULL) {}

int relation() {
return fa->c[1] == this;
}
} *root, _pool[MAXN], *_curr;

Splay() : root(NULL) {}

void init() {
_curr = _pool;
}

void rotate(Node *u) {
Node *o = u->fa;
int x = u->relation();

u->fa = o->fa;
if (u->fa) u->fa->c[o->relation()] = u;

o->c[x] = u->c[x ^ 1];
if (u->c[x ^ 1]) u->c[x ^ 1]->fa = o;

u->c[x ^ 1] = o;
o->fa = u;
}

Node *splay(Node *u, Node *targetFa = NULL) {
while (u->fa != targetFa) {
if (u->fa->fa == targetFa) rotate(u);
else if (u->relation() == u->fa->relation()) rotate(u->fa), rotate(u);
else rotate(u), rotate(u);
}
if (!targetFa) root = u;
return u;
}

double predSlope(Node *u) {
return u->pred ? (u->y - u->pred->y) / (u->x - u->pred->x) : 1.0 / 0.0;
}

double succSlope(Node *u) {
return u->succ ? (u->y - u->succ->y) / (u->x - u->succ->x) : -1.0 / 0.0;
}

Node *insert(double x, double y) {
if (!root) {
root = new (_curr++) Node(NULL, x, y);
return root;
}

Node **u = &root, *fa = NULL;

while (*u && dcmp(x, (*u)->x)) {
fa = *u;
u = &(*u)->c[dcmp(x, (*u)->x) > 0];
}

if (*u) {
if (dcmp((*u)->y, y) >= 0) return splay(*u);
(*u)->y = y;
} else {
(*u) = new (_curr++) Node(fa, x, y);

if ((*u)->relation()) {
(*u)->succ = fa->succ;
(*u)->pred = fa;
if (fa->succ) fa->succ->pred = *u;
fa->succ = *u;
} else {
(*u)->pred = fa->pred;
(*u)->succ = fa;
if (fa->pred) fa->pred->succ = *u;
fa->pred = *u;
}
}

Node *v = *u;
if (dcmp(predSlope(v), succSlope(v)) <= 0) {
splay(v->pred);
splay(v->succ, v->pred);
v->pred->succ = v->succ;
v->succ->pred = v->pred;
v->succ->c[0] = NULL;
return NULL;
}

while (v->pred && dcmp(predSlope(v->pred), predSlope(v)) <= 0)
v->pred = v->pred->pred;
if (v->pred) {
splay(v->pred);
splay(v, v->pred);
v->pred->succ = v;
}
v->c[0] = NULL;

while (v->succ && dcmp(succSlope(v->succ), succSlope(v)) >= 0)
v->succ = v->succ->succ;
if (v->succ) {
splay(v->succ);
splay(v, v->succ);
v->succ->pred = v;
}
v->c[1] = NULL;

return splay(v);
}

Node *find(double slope) {
Node *u = root;
while (true) {
if (dcmp(predSlope(u), slope) < 0) u = u->c[0];
else if (dcmp(succSlope(u), slope) > 0) u = u->c[1];
else return u;
}
}
} splay;

int main() {
int n, S;
scanf("%d %d", &n, &S);

double ans = S;
splay.init();
for (int i = 0; i < n; i++) {
double a, b, rate;
scanf("%lf %lf %lf", &a, &b, &rate);

double slope = -a / b;
if (i) {
Splay::Node *u = splay.find(slope);
ans = std::max(ans, a * u->x + b * u->y);
}

double y = ans / (a * rate + b);
double x = y * rate;

splay.insert(x, y);
}
printf("%.6f\n", ans);

return 0;
}

CDQ 分治

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

const int MAXN = 1000005;
const double EPS = 1e-9;

int dcmp(double a, double b = 0) {
double d = a - b;
return std::abs(d) <= EPS ? 0 : (d > 0 ? 1 : -1);
}

struct Data {
double a, b, rate, x, y, slope, f;
int id;

bool operator<(const Data &rhs) const {
return dcmp(slope, rhs.slope) > 0;
}
} a[MAXN];

double slope(const Data &a, const Data &b) {
return (a.y - b.y) / (a.x - b.x);
}

void divide(Data *l, Data *r, double &ans) {
if (l + 1 == r) {
ans = std::max(ans, l->f);
l->y = ans / (l->a * l->rate + l->b);
l->x = l->y * l->rate;
return;
}

static Data q[MAXN];
Data *mid = l + ((r - l) >> 1), *tl = q, *tr = q + (mid - l);
for (Data *p = l; p < r; p++) {
if (p->id < mid - a) *tl++ = *p;
else *tr++ = *p;
}
std::copy(q, tr, l);

divide(l, mid, ans);

Data *L = q + 1, *R = q;
for (Data *p = l; p < mid; p++) {
while (L < R && dcmp(slope(*(R - 1), *R), slope(*R, *p)) <= 0) --R;
*++R = *p;
}
for (Data *p = mid; p < r; p++) {
while (L < R && dcmp(slope(*L, *(L + 1)), p->slope) >= 0) ++L;
p->f = std::max(p->f, p->a * L->x + p->b * L->y);
}

divide(mid, r, ans);

tl = l, tr = mid;
for (Data *p = q; p < q + (r - l); p++) {
if (tr >= r || (tl < mid && dcmp(tl->x, tr->x) <= 0)) *p = *tl++;
else *p = *tr++;
}
std::copy(q, q + (r - l), l);
}

int main() {
int n, S;
scanf("%d %d", &n, &S);

for (int i = 0; i < n; i++) {
scanf("%lf %lf %lf", &a[i].a, &a[i].b, &a[i].rate);
a[i].slope = -a[i].a / a[i].b;
a[i].id = i;
}

std::sort(a, a + n);
double ans = S;
divide(a, a + n, ans);

printf("%.6f\n", ans);

return 0;
}