P4027 [NOI2007] 货币兑换

类似的题目有一个性质：如果在某操作是有收益的，那么一定全部操作；否则全部不操作。所以不必考虑卖出、买入多少的问题，只考虑在何处买入、卖出的问题。

记 $f _ i$ 为第 $i$ 天的最大现金值。考虑从某一天转移。如果一个 $f _ i$ 已经求出，可以直接根据 $A, B, Rate$ 算出 $A, B$ 金券的数量，记为 $x _ i, y _ i$ ，那么有转移方程 $f _ i = \max _ {j < i} x _ j A_ i + y _ j B _ i$ 。

从 $a$ 转移到 $i$ 比从 $b$ 转移到 $i$ 优 $x _ a < x _ b$ 当且仅当：

$$
\begin {array} {c}
x _ a A _ i + y _ a B _ i & < & x _ b A _ i + y _ b B _ i \\
(y _ b - y _ a) B _ i & < & (x _ b - x _ a) A _ i \\
\frac {(y _ b - y _ a)} {(x _ b - x _ a)} & < & \frac {B _ i} {A _ i}
\end {array}
$$

$x _ i$ 没有单调性，考虑 CDQ 分治，左侧按照 $x$ 排序，构建凸包，右侧按照 $k$ 排序查询。

查看代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
const double inf = 1e9, eps = 1e-9;
int n, p[N], q[N];
double A[N], B[N], R[N], f[N], X[N], Y[N], K[N];
double slp (int i, int j)
{
    if (X[i] == X[j]) return inf;
    return (Y[i] - Y[j]) / (X[i] - X[j]);
}
void cdq (int l, int r)
{
    if (l == r)
    {
        f[l] = max(f[l], f[l - 1]);
        Y[l] = f[l] / (A[l] * R[l] + B[l]);
        X[l] = Y[l] * R[l];
        return;
    }
    int mid = l + r >> 1;
    cdq(l, mid);
    for (int i = l; i <= r; ++i) p[i] = i;
    sort(p + l, p + mid + 1, [&](int i, int j) { return X[i] < X[j]; });
    sort(p + mid + 1, p + r + 1, [&](int i, int j) { return K[i] > K[j]; });
    int hd = 1, tl = 0;
    for (int i = l; i <= mid; ++i)
    {
        while (hd < tl && slp(q[tl], p[i]) > slp(q[tl - 1], q[tl])) --tl;
        q[++tl] = p[i];
    }
    for (int i = mid + 1; i <= r; ++i)
    {
        while (hd < tl && slp(q[hd], q[hd + 1]) > K[p[i]]) ++hd;
        f[p[i]] = max(f[p[i]], X[q[hd]] * A[p[i]] + Y[q[hd]] * B[p[i]]);
    }
    cdq(mid + 1, r);
}
int main ()
{
    scanf("%d%lf", &n, &f[0]);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%lf%lf%lf", &A[i], &B[i], &R[i]);
        K[i] = -A[i] / B[i];
    }
    cdq(1, n);
    printf("%.3lf", f[n]);
    return 0;
}