Description
最初你有 S 块钱, 有 N 天给你来兑换货币, 求最大获利.
一共只有两种货币 A , B .
对于每一天, 给定 3 个系数 A[i], B[i], Rate[i]
A[i] 表示当天 A 货币的单位价值, B[i] 表示当前 B 货币的单位价值.
第\(i\)天你可以进行以下两种操作: (可以执行多次)
① 将 OP% 的 A 货币和 OP% 的 B 货币卖出.
② 按照 A : B = Rate[i] 的比例, 用一部分的钱买入货币.
\(n \le 100000\)
Analysis
考虑假如有一天买货币没有用完所有钱更优, 说明这里的前用了后面赚不回来
同理可知: 要么一次性买入货币买光所有钱, 要么一次卖光所有货币
我们将相邻的买卖分为一组
记\(f[i]\)为第\(i\)天(在买之前)最多能有多少钱
于是\(f[i] = \max\{f[i-1], D[j] * A[i] + C[j] * B[i]\}\)
其中\(C[i] = \frac{f[i]}{A[i]*Rate[i] + B[i]}\) 即花光钱能买多少个\(B\)货币
\(D[i] = C[i] * Rate[i]\)即花光钱能买多少个\(A\)货币
这是一个可以斜率优化的式子.
但是注意到\(A,B,C,D\)什么的都并没有单调性
Solution 1
动态维护凸壳
Solution 2
注意到转移只与前面求出来的量有关
那么我们可以进行cdq分治
这样我们就可以排序建凸包, 排序切线询问.
Notice
不是一般序列上的斜率优化, 最好使用\(\det\)
对于切线询问, 除了可以用斜率判, 也可以直接根据答案的单峰性判断, 具体见代码
另外, 凸包比较还是用\(\le ,\ge\)这两个符号好一些
Code
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <iostream>
#define rep(i,a,b) for (int i = (a); i <= (b); ++ i)
#define per(i,a,b) for (int i = (a); i >= (b); -- i)
#define For(i,a,b) for (int i = (a); i < (b); ++ i)
using namespace std;
const int M = 1e5 + 7;
typedef double db;
inline int ri(){
int x = 0; bool f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = 0;
for (; isdigit(c); c = getchar()) x = x*10+c-48;
return f ? x : -x;
}
int n;
db f[M];
db A[M], B[M], C[M], D[M], R[M];
inline db det(db x, db y, db vx, db vy) {return x * vy - y * vx;}
inline bool side(int x, int y, int z) {return det(D[y]-D[x], C[y]-C[x], D[z]-D[x], C[z]-C[x]) >= 0;}
inline db calc(int x, int y) {return D[x] * A[y] + C[x] * B[y];}
inline db V(int x) {return - A[x] / B[x];}
inline bool cmp1(int x, int y) {return D[x] < D[y];}
inline bool cmp2(int x, int y) {return V(x) > V(y);}
void cdq(int l, int r){
static int q[M], v[M];
if (l == r) {
f[l] = max(f[l], f[l-1]);
C[l] = f[l] / (A[l] * R[l] + B[l]);
D[l] = C[l] * R[l];
return;
}
int mid = l+r >> 1;
cdq(l, mid);
rep (i, l, mid) q[i] = i;
sort(q+l, q+mid+1, cmp1);
int h = l, t = l-1;
rep (i, l, mid){
while (h < t && side(q[t-1], q[t], q[i]) ) --t;
q[++t] = q[i];
}
rep (i, mid+1, r) v[i] = i;
sort(v+mid+1, v+r+1, cmp2);
rep (i, mid+1, r){
int y = v[i];
while (h < t && calc(q[h], y) <= calc(q[h+1], y)) ++h;
f[y] = max(f[y], calc(q[h], y));
}
cdq(mid+1, r);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in", "r", stdin);
#endif
scanf("%d%lf", &n, &f[0]);
rep (i, 1, n) scanf("%lf%lf%lf", &A[i], &B[i], &R[i]);
cdq(1, n);
printf("%.3lf\n", f[n]);
return 0;
}