RenaMoe's Blog

念念不忘，必有回响

0%

题解 P4027 [NOI2007]货币兑换

发表于 分类于 ， Valine：

有 A,B 两种金券，它们每天的价值都不同，在第 i 天时分别为 \(A_i,B_i\)，你可以用手中的金券换取相应价值的钱，或用钱兑换相同价值的金券，但兑换到的两种金券的数量之比是一个定值，这个定值在第 i 天为 \(R_i\)。

现给出 n 天中两种金券的价值，R，以及你初始时拥有的资金 S，求 n 天后你最多能有多少钱。

我来做经典的CDQ维护凸包了qwq。

思路

DP

如果第 i 天卖出相对于第 j 天买入有利可图，那么肯定全部卖出。

考虑 DP，我们可以推出转移方程： \[ f_i=\frac{f_jR_j}{A_jR_j+B_j}\times A_i + \frac{f_j}{A_jR_j+B_j}\times B_i \] 我们设 A,B 券分别买入的数量为 \(x_i=\frac{f_iR_i}{A_iR_i+B_i},y_i=\frac{f_i}{A_iR_i+B_i}\) 。

得到：

\[ f_i=A_ix_j + B_iy_j\\ y_j=-\frac{A_i}{B_i}x_j+\frac{f_i}{B_j} \]

啊这是个斜率优化欸，维护上凸包使得直线的 \(b=\frac{f_i}{B_j}\) 最大。

我上来就单调队列线性时间内干过去。。。啊怎么不太对。

发现斜率 \(-\frac{A_i}{B_i}\) 不是单调的，需要手写平衡树维护凸包什么的。

这辈子不可能写这种东西的，虽然 cmd2001 学长有博客讲用 STL set 维护动态凸包。

于是我们来学习 CDQ 维护斜率优化凸包。

CDQ 维护斜率优化的凸包

CDQ 分治的话，要每次计算左半边对右半边的贡献。

可以让左区间按 \(x_i\) 排序，保持右区间按斜率 \(k_i=\frac{A_i}{B_i}\) 单调递增有序。

左区间就可以通过栈维护一个斜率单调递减的凸包来更新右区间的答案。

每一层分治就这么 \(O(n)\) 解决，总复杂度 \(O(nlogn)\)。

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 <cmath>
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;

namespace RenaMoe {
template <typename TT> inline void read(TT &x) {}

const int N = 1e5 + 9;
const double Eps = 1e-7;// 注意精度误差
const double INF = 1e8;

struct Ask {
    double k, x, y, a, b, r;// 分别表示：斜率,x,y,A,B,R
    int id;
};

int n, s;
int stk[N];
Ask q[N], tmp[N];
double f[N];

inline bool cmp(const Ask &x, const Ask &y) {
    return x.k < y.k;
}

// 求斜率
inline double get_slope(int i, int j) {
    if (fabs(q[i].x - q[j].x) <= Eps) return INF;
    return (q[i].y - q[j].y) / (q[i].x - q[j].x);
}

void solve(int l, int r) {
    if (l == r) {
        // 此时1~l-1的答案都已经处理完，更新f[l]
        f[l] = max(f[l], f[l-1]);
        q[l].y = f[l] / (q[l].a * q[l].r + q[l].b), q[l].x = q[l].y * q[l].r;
        return;
    }
    // 按id划分左右区间
    int mid = (l + r) >> 1, q1 = l, q2 = mid+1;
    for (int i = l; i <= r; ++i) {
        if (q[i].id <= mid) tmp[q1++] = q[i];
        else tmp[q2++] = q[i];
    }
    for (int i = l; i <= r; ++i) q[i] = tmp[i];
    // 先处理左区间
    solve(l, mid);
    // 维护左区间斜率单调递减的凸包
    int top = 0;
    for (int i = l; i <= mid; ++i) {
        while (top >= 2 && get_slope(stk[top-1], stk[top]) < get_slope(stk[top], i) + Eps) top--;
        stk[++top] = i;
    }
    // 用左区间的凸包更新右区间答案
    for (int i = mid+1; i <= r; ++i) {
        while (top >= 2 && get_slope(stk[top-1], stk[top]) <= q[i].k + Eps) top--;
        int j = stk[top];
        f[q[i].id] = max(f[q[i].id], q[i].a * q[j].x + q[i].b * q[j].y);// 注意是q[i].id，不是i
    }
    // 处理右区间
    solve(mid+1, r);
    // 按x单调递增归并排序，以作为上一层的左区间
    q1 = l, q2 = mid+1;
    for (int i = l; i <= r; ++i) {
        if (q1 <= mid && (q2 > r || q[q1].x < q[q2].x + Eps)) tmp[i] = q[q1++];
        else tmp[i] = q[q2++];
    }
    for (int i = l; i <= r; ++i) q[i] = tmp[i];
}

inline void main() {
    read(n), read(s);
    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].id = i;
    }
    sort(q+1, q+n+1, cmp);// 先按斜率单调递增排序
    f[0] = s;
    solve(1, n);
    printf("%.3lf\n", f[n]);
}
}

int main() {
    RenaMoe::main();
    return 0;
}