【题解】BZOJ 1492 [NOI2007]货币兑换Cash

请注意,本文编写于 175 天前,最后修改于 175 天前,其中某些信息可能已经过时。

Problem

传送门 >ω<

这是一道烂大街的题就不放题面了

Thought

首先肯定存在某种最优方案满足每次操作卖掉所有金券或者将钱全部换为金券

对于某种没有卖掉/买入全部金券的方案,预见到一个操作如果能赚钱,不如将所有钱全部投入其中
如果有另外一个选择能赚更多钱,不如现在就暂时不进行操作

毕竟上帝视角(雾

设 $f[i]$ 为第 $i$ 天手上能够换到多少钱,转移显然

$$ f[i]=max(\frac{f[j]*(rate[j]*a[i]+b[i])}{rate[j]*a[j]+b[j]}) $$

为了方便,将第 $j$ 天 $A,B$ 卷数目设为 $A[j],B[j]$,其中 $A[j]=\frac{f[j]rate[j]}{rate[j]*a[j]+b[j]},B[j]=\frac{f[j]}{rate[j]*a[j]+b[j]}$

那么式子化简为

$$ f[i]=max(A[j]*a[i]+B[j]*b[i],f[i-1]) $$

$f[i-1]$ 存下来比一下就好了,但是 $A[j]*a[i]+B[j]*b[i]$ 怎么处理?

发现这个式子存在两个变量,且次数为 $1$,考虑将其变为斜率式,将最大值转化为截距最大,也就是说

$$ f[i]=A[j]*a[i]+B[j]*b[i]\\ \Updownarrow\\ B[j]=-\frac{a[i]}{b[i]}A[j]+\frac{f[i]}{b[i]} $$

该式子可看做以 $B[j]$ 为纵坐标,$A[j]$ 为横坐标,$-\frac{a[i]}{b[i]}$ 为斜率,$\frac{f[i]}{b[i]}$ 为截距的直线
也就是求过点 $(A[j],B[j])$ 且斜率为 $-\frac{a[i]}{b[i]}$ 的直线的最大截距

显然,如果使得截距最大,点 $(A[j],B[j])$ 必然在凸包上,所以维护一个凸包并且在凸包上二分即可找到最大的截距

由于需要保证在时间有序的基础上斜率有序(方便维护凸包),在这里使用 $CDQ$ 分治的方法:

第一维按照斜率排序
第二维归并维护时间

$cdq(l,r)$
​ $sort\ by\ x$
​ $cdq(l,mid)$
​ $use\ left\ to\ update\ right$
​ $cdq(mid+1,r)$
​ $merge(l,r)$

Code

#include <bits/stdc++.h>
using namespace std;
#define double long double
#define mid ((l + r) >> 1)
#define eps 1e-9
const int N = 1000010;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
int n , s;
double f[N];
struct data {
    double a , b , rate , k;
    int id;
    void in() {
        scanf("%llf %llf %llf" , &a , &b , &rate);
        k = - a / b;
    }
    bool operator < (const data a) const {return a.k - k > eps;}
}a[N] , na[N];
struct point {
    double x , y;
    bool operator < (const point a) const {return fabs(x - a.x) <= eps ? a.y - y > eps : a.x - x > eps;}
}p[N] , np[N];
int sta[N];
double get(int a , int b) {return fabs(p[a].x - p[b].x) <= eps ? - 10000000 : (p[a].y - p[b].y) / (p[a].x - p[b].x);}
void cdq(int l , int r) {
    if(l == r) {
        f[l] = max(f[l] , f[l - 1]);
        p[l].x = f[l] * a[l].rate / (a[l].rate * a[l].a + a[l].b);
        p[l].y = f[l] / (a[l].rate * a[l].a + a[l].b);
        return ;
    }
    int l1 = l , l2 = mid + 1;
    for(int i = l ; i <= r ; ++ i) {
        if(a[i].id <= mid)
            na[l1 ++] = a[i];
        else
            na[l2 ++] = a[i];
    }
    for(int i = l ; i <= r ; ++ i)
        a[i] = na[i];
    cdq(l , mid);
    int top = 0;
    for(int i = l ; i <= mid ; ++ i) {
        while(top >= 2 && get(i , sta[top]) - get(sta[top] , sta[top - 1]) > eps) sta[top --] = 0;
        sta[++ top] = i;
    }
    for(int i = mid + 1 ; i <= r ; ++ i) {
        while(top >= 2 && a[i].k - get(sta[top - 1] , sta[top]) > eps) sta[top --] = 0;
        int id = sta[top];
        f[a[i].id] = max(f[a[i].id] , p[id].x * a[i].a + p[id].y * a[i].b);
    }
    cdq(mid + 1 , r);
    l1 = l , l2 = mid + 1;
    for(int i = l ; i <= r ; ++ i) {
        if((p[l1] < p[l2] || l2 > r) && l1 <= mid)
            np[i] = p[l1 ++];
        else
            np[i] = p[l2 ++];
    }
    for(int i = l ; i <= r ; ++ i)
        p[i] = np[i];
}
int main() {
    #ifndef ONLINE_JUDGE
        freopen("in" , "r" , stdin);
    #endif
    n = read(); f[1] = read();
    for(int i = 1 ; i <= n ; ++ i) {a[i].in(); a[i].id = i;}
    sort(a + 1 , a + n + 1);
    cdq(1 , n);
    printf("%.3llf\n" , f[n]);
    return 0;
}
Comments

添加新评论