题目链接：LOJ 2353

小 Y 最近在一家金券交易所工作。该金券交易所只发行交易两种金券：$A$ 纪念券（以下简称 $A$ 券）和 $B$ 纪念券（以下简称 $B$ 券）。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。每天随着市场的起伏波动，两种金券都有自己当时的价值，即每一单位金券当天可以兑换的人民币数目。我们记录第 $i$ 天中 $A$ 券和 $B$ 券的价值分别为 $A_i$ 和 $B_i$（元 / 单位金券）。为了方便顾客，金券交易所提供了一种非常方便的交易方式：比例交易法。比例交易法分为两个方面：

• 卖出金券：顾客提供一个 $[0,100]$ 内的实数 $\text{OP}$ 作为卖出比例，其意义为：将 $\text{OP}\%$ 的 $A$ 券和 $\text{OP}\%$ 的 $B$ 券以当时的价值兑换为人民币。
• 买入金券：顾客支付 $\text{IP}$ 元人民币，交易所将会兑换给用户总价值为 $\text{IP}$ 的金券，并且，满足提供给顾客的 $A$ 券和 $B$ 券的比例在第 $i$ 天恰好为 $Rate_i$。

注意：同一天内可以进行多次操作。

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

数据范围：$1 \le n \le 10 ^ 5$，$0 < A_i, B_i \le 10$，$0 < Rate_i \le 100$，$0 \le \text{答案}\le 10 ^ 9$。

Solution

我们先贪心地想：如果在第 $i$ 天买入或者卖出有利可图，那么一定会在那天用所有的钱来买入、或者把所有的金券卖出。

这样我们就可以定义 $\text{DP}$ 状态：设 $f_i$ 表示第 $i$ 天结束时（完成当天交易后）可以得到的最多的钱数。我们可以算出用 $f_i$ 的钱可以在当天买到的两种金券数量分别为：

$$ x_i = \frac{f_i \times Rate_i}{A_i \times Rate_i + B_i} \\ y_i = \frac{f_i}{A_i \times Rate_i + B_i} $$

得到转移方程：

$$ f_i = \max(f_{i - 1}, \max\{A_i\times x_j + B_i\times y_j\})\quad (0 \le j < i) $$

先不考虑前缀 $\max$，即为：

$$ f_i = \max\{A_i \times x_j + B_i \times y_j\}\quad (0 \le j < i) $$

把这个式子转化成直线方程：

$$ y_j = -\frac{A_i}{B_i}x_j + \frac{f_i}{B_i} $$

截距就是 $\frac{f_i}{B_i}$，由于对于当前的 $i$，$B_i$ 是定值，那么我们要最大化 $f_i$ 就是最大化截距。

考虑斜率优化，假设 $x_k<x_j$，那么 $j$ 比 $k$ 更好当且仅当 $K(j,k)>-\frac{A_i}{B_i}$。但是注意到 $x_i$ 和斜率都不是递增的，因此不满足单调性，也就不能用单调队列优化了。

我们需要动态维护一个上凸壳（斜率恒负），可以使用平衡树或者 $\text{CDQ}$ 分治。但是 $\text{CDQ}$ 比平衡树（其实是我不会）好写很多，这里只介绍 $\text{CDQ}$ 分治的做法。

我们先按照决策点（也就是说按照斜率 $-\frac{A_i}{B_i}$）排序，对其进行分治。把区间 $[l,r]$ 中的决策点按照下标分成 $\le m$ 和 $> m$ 的两个部分，对左区间 $[l,m]$ 递归计算。我们在递归后按照 $x$ 排序，这样使得左区间递归完后的 $x$ 是有序的。

我们对左区间构建一个上凸壳。右区间由于斜率递增，可以 $\mathcal O(n)$ 直接在凸包上找到截距最大的直线，通过转移方程转移即可。计算完左区间的贡献后，我们递归计算右区间 $[m+1,r]$，最后如上文所述，把区间 $[l,r]$ 按照 $x$ 归并排序。

由于所有的排序都是 $\mathcal O(n)$ 的，转移也是 $\mathcal O(n)$ 的，故总复杂度为 $\mathcal O(n\log n)$。只不过常数较大。

时间复杂度：$\mathcal O(n\log n)$。

Code

#include <cstdio>
#include <cmath>
#include <algorithm>

const int N = 1e5 + 5;
const double eps = 1e-8;

int n, s[N];
double f[N], x[N], y[N];

struct Data {
    double A, B, R, x, y, k;
    int idx;
    bool operator<(const Data &b) const {
        return k < b.k;
    }
} q[N], t[N];

double slope(int i, int j) {
    if (std::fabs(q[i].x - q[j].x) < eps) return 1e9;
    return (q[i].y - q[j].y) / (q[i].x - q[j].x);
}
void CDQ(int l, int r) {
    if (l == r) {
        int i = q[l].idx;
        f[i] = std::max(f[i - 1], f[i]);
        q[i].x = f[i] * q[i].R / (q[i].R * q[i].A + q[i].B);
        q[i].y = f[i] / (q[i].R * q[i].A + q[i].B);
        return;
    }
    int m = (l + r) >> 1;
    for (int j = l, k = m + 1, i = l; i <= r; i++) {
        if (q[i].idx <= m) {
            t[j++] = q[i];
        } else {
            t[k++] = q[i];
        }
    }
    for (int i = l; i <= r; i++) q[i] = t[i];
    CDQ(l, m);
    int tp = 0;
    for (int i = l; i <= m; i++) {
        while (tp >= 2 && slope(s[tp - 1], s[tp]) < slope(s[tp], i)) tp--;
        s[++tp] = i;
    }
    for (int i = m + 1; i <= r; i++) {
        while (tp >= 2 && slope(s[tp - 1], s[tp]) < q[i].k) tp--;
        int j = s[tp];
        f[q[i].idx] = std::max(f[q[i].idx], q[i].A * q[j].x + q[i].B * q[j].y);
    }
    CDQ(m + 1, r);
    for (int i = l, j = m + 1, k = l; i <= m || j <= r; ) {
        if (j > r || (i <= m && q[i].x < q[j].x)) {
            t[k++] = q[i++];
        } else {
            t[k++] = q[j++];
        }
    }
    for (int i = l; i <= r; i++) q[i] = t[i];
}
int main() {
    scanf("%d%lf", &n, &f[0]);
    for (int i = 1; i <= n; i++) {
        scanf("%lf%lf%lf", &q[i].A, &q[i].B, &q[i].R);
        q[i].k = -q[i].A / q[i].B;
        q[i].idx = i;
    }
    std::sort(q + 1, q + n + 1);
    CDQ(1, n);
    printf("%.3lf\n", f[n]);
    return 0;
}