P4027 [NOI2007]货币兑换

发表于 | 阅读数

有 $A,B$ 两种金券，它们每天的价值都不同，在第 $i$ 天时分别为 $A_i,B_i$你可以用手中的金券换取相应价值的钱，或用钱兑换相同价值的金券，但兑换到的两种金券的数量之比是一个定值，这个定值在第 $i$ 天为 $R_i$
现给出 $n$天中两种金券的价值$R$，以及你初始时拥有的资金 $S$，求 $n$ 天后你最多能有多少钱。

注：一定存在一种最优方案，满足：每次兑换金券花光所有的钱，每次换钱时花掉所有的金券。

有提示了：一定是某一天用完所有，然后某一天再卖掉所有。

设$dp[i]$表示第$i$天，买完拥有最多$A$卷个数。

全部无规律,但是应该是维护一个上凸包。

动态凸包代补

CDQ分治

  • 将所有决策点（从$1$到$n$）存入数组$p$中。
  • p中的点按斜率从大到小排序。
  • 设当前处理的决策点范围为$l到r$，对应$p$数组中的·第$fl$到第$fr$个元素。
  • 把前$mid$个询问放在左边，后$mid$个放在右边
  • 递归处理$(l,mid)$
  • 由于斜率右侧无影响，为单调，所有将左侧建立凸包，右侧单指针寻找即可。
  • 最后处理$(mid+1,r)$,并且合并使得$(l,r)$按照$x$单调增排序。
代码 
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


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
const db eps = 1e-9;
const db inf = 1e18;
db dp[N], a[N], b[N], r[N], idx[N];

db X(int x) { return dp[x] * r[x] / (a[x] * r[x] + b[x]); }
db Y(int x) { return dp[x] / (a[x] * r[x] + b[x]); }
db K(int x) { return -1 * a[x] / b[x]; }
bool cmp1(int a, int b) { return X(a) < X(b); } // sort by y
bool cmp2(int a, int b) { return K(a) > K(b); } // sort by slope
db slope(int a, int b)
{
    if (fabs(X(a) - X(b)) < eps)
    {
        return inf;
    }
    return (Y(a) - Y(b)) / (X(a) - X(b));
}
int q[N];
void solve(int l, int r)
{
    if (l == r)
    {
        dp[l] = max(dp[l], dp[l - 1]);
        return;
    }

    int mid = (l + r) >> 1;
    solve(l, mid);
    sort(idx + l, idx + mid + 1, cmp1);
    sort(idx + mid + 1, idx + r + 1, cmp2);
    int head = 1, tail = 0;
    for (int i = l; i <= mid; i++)
    {
        int now = idx[i];
        while (head < tail && slope(now, q[tail]) > slope(q[tail - 1], q[tail]))
            tail--;
        q[++tail] = now;
    }

    for (int i = mid + 1; i <= r; i++)
    {
        int now = idx[i];
        while (head < tail && slope(q[head + 1], q[head]) > K(now))
            ++head;
        dp[now] = max(dp[now], X(q[head]) * a[now] + Y(q[head]) * b[now]);
    }
    for (int i = l; i <= r; i++)
        idx[i] = i;
    solve(mid + 1, r);
}
int n;
int main()
{
    scanf("%d%lf", &n, &dp[1]);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lf%lf%lf", &a[i], &b[i], &r[i]);
        idx[i] = i;
    }
    solve(1, n);

    printf("%.3lf", dp[n]);
    return 0;
}