洛谷P4027 [NOI2007]货币兑换

Description
小Y最近在一家金券交易所工作。该金券交易所只发行交易两种金券：A纪念券（以下简称A券）和 B纪念券（以下
简称B券）。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。每天随着市场的起伏波动，
两种金券都有自己当时的价值，即每一单位金券当天可以兑换的人民币数目。我们记录第 K 天中 A券 和 B券 的
价值分别为 AK 和 BK（元/单位金券）。为了方便顾客，金券交易所提供了一种非常方便的交易方式：比例交易法
。比例交易法分为两个方面：（a）卖出金券：顾客提供一个 [0,100] 内的实数 OP 作为卖出比例，其意义为：将
 OP% 的 A券和 OP% 的 B券 以当时的价值兑换为人民币；（b）买入金券：顾客支付 IP 元人民币，交易所将会兑
换给用户总价值为 IP 的金券，并且，满足提供给顾客的A券和B券的比例在第 K 天恰好为 RateK；例如，假定接
下来 3 天内的 Ak、Bk、RateK 的变化分别为：

假定在第一天时，用户手中有 100元 人民币但是没有任何金券。用户可以执行以下的操作：

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

Input
输入第一行两个正整数N、S，分别表示小Y能预知的天数以及初始时拥有的钱数。接下来N行，第K行三个实数AK、B
K、RateK，意义如题目中所述。对于100%的测试数据，满足：0<AK≤10；0<BK≤10；0<RateK≤100；MaxProfit≤1
0^9。
【提示】
1.输入文件可能很大，请采用快速的读入方式。
2.必然存在一种最优的买卖方案满足：
每次买进操作使用完所有的人民币；
每次卖出操作卖出所有的金券。
 
Output
只有一个实数MaxProfit，表示第N天的操作结束时能够获得的最大的金钱数目。答案保留3位小数。

Sample Input
```
3 100
1 1 1
1 2 2
2 2 3
```
Sample Output
```
225.000
```
HINT

脑袋抽了，居然没有发现每一天只有三种操作：全买、全卖和不进行买卖……
~~终于会斜率优化了，用凸包，用凸包，用凸包！~~

观察到上面的贪心性质我们已经有了一个$O(n^2)$的优秀做法：
$$f_i=max{\{\frac{f_j}{a_jR_j+b_j}R_ja_i+\frac{f_j}{a_jR_j+b_j}b_i,f_{i-1}\}}$$

然后自然尝试将它化成斜率式：

$$\frac{f_j}{a_jR_j+b_j}b_i=-\frac{f_j}{a_jR_j+b_j}R_ja_i+f_i \\
\to \frac{f_j}{a_jR_j+b_j}=-\frac{f_j}{a_jR_j+b_j}\frac{a_i}{b_i}R_j+\frac{f_i}{b_i}$$

发现$f_i$已经与截距正相关，那么我们得到了这样的直线：
$$y=-\frac{a_i}{b_i}x+\frac{f_i}{b_i}$$
每一个决策相当于平面上的点：
$$(\frac{f_j\cdot R_j}{a_jR_j+b_j},\frac{f_j}{a_jR_j+b_j})$$
那么我们只要对前面的所有决策维护一个凸包，二分斜率就可以了。

但是用splay维护凸包是不是太不优雅太难写太繁琐了呢？

当当当当~在半天的研究之后，终于实现了用set维护支持二分斜率的凸包的骚操作，让您摆脱splay血wa的烦恼：

```
//采用set维护可二分斜率的半凸包
namespace Convex {
    #define eps 1e-8
    //自己调整eps，下面是符号函数
    inline int sgn(double x) {return (x > -eps) - (x < eps);}
    //这里采用数组记录左右斜率的方法回避set中变量为const的问题
    double ls[maxn], rs[maxn];
    int cnt, D = 1;
    struct node {
        double x, y; int id;
        bool operator < (const node & A) const {
        //在二分斜率的时候我们令D为1，在普通插入的时候令D为0。这样就可以切换两种比较模式
            if(D) return sgn(x - A.x) ? sgn(x - A.x) < 0 : sgn(y - A.y) > 0;
            return sgn(rs[id] - ls[A.id]) > 0;
        }
    };
    //u -> v;获得斜率
    inline double Gslope(const node &u, const node &v) {
        return (v.y - u.y) / (v.x - u.x);
    }
    set<node > st;
    //使用iterator查找前驱后继
    set<node >::iterator it, now, pre, nxt;
    void init(const double &x, const double &y) {
        st.insert((node){x, y, 1});
        //因为是上半凸包，左到右斜率递减，初始化成+/-inf可以省很多事
        ls[++cnt] = (1.0/0.0);
        rs[cnt] = -(1.0/0.0);
    }
    void insert(const double &x, const double &y) {
    	now = st.insert((node) {x, y, ++cnt}).first;
    	//如果有前驱获得前驱 
        if(now != st.begin()) it = now, --it, pre = it;
        //同样的初始化
        ls[cnt] = (1.0/0.0), rs[cnt] = -(1.0/0.0);
        it = now, ++it, nxt = it;
        if(now != st.begin())
            ls[now -> id] = Gslope(*pre, *now);
        if(nxt != st.end()) 
            rs[now -> id] = Gslope(*now, *nxt);
        if(rs[now -> id] < ls[now -> id]) {
        	if(now != st.begin()) rs[pre -> id] = ls[now -> id];
            if(nxt != st.end()) ls[nxt -> id] = rs[now -> id];
        }
        //如果当前点不在凸包上直接删掉
        else return st.erase(now), void();
        //弹弹弹，根据斜率单调性弹走内部点	
        if(now != st.begin())
            while(sgn(rs[pre -> id] - ls[pre -> id]) > 0) {
                it = pre, --pre;
                rs[pre -> id] = ls[now -> id] = Gslope(*pre, *now);
                st.erase(it);
            }
        if(nxt != st.end())
            while(sgn(rs[nxt -> id] - ls[nxt -> id]) > 0) {
                it = nxt, ++nxt;
                rs[now -> id] = ls[nxt -> id] = Gslope(*now, *nxt);
                st.erase(it);
            }
    }
    //二分斜率，妙用空余的0标号，记得改D
    int GetK(double k) {
        rs[0] = ls[0] = k, D = 0;
        it = st.lower_bound((node) {0, 0, 0});
        return D = 1, it -> id;
    }
    #undef eps
}
```

实际时间测试：
在开O2情况下的时间：
![图片标题](https://leanote.com/api/file/getImage?fileId=5bdea863ab644149c50080d9)

而这个是一般情况下开着O2的cdq的用时：
![图片标题](https://leanote.com/api/file/getImage?fileId=5bdea887ab644149c50080f9)

因为个人的代码中有很多空格，所以实际上代码长度基本上增加了50%

这个好写又好调的斜率凸包板子，您值得拥有！
另外，这道题数据好像有点水，凸包wa了也能过……
```
// luogu-judger-enable-o2
#include<cstdio>
#include<set>
using namespace std;
const int maxn = 1e5 + 5;
namespace Convex {
    #define eps 1e-8
    inline int sgn(double x) {return (x > -eps) - (x < eps);}
    double ls[maxn], rs[maxn];
    int cnt, D = 1;
    struct node {
        double x, y; int id;
        bool operator < (const node & A) const {
            if(D) return sgn(x - A.x) ? sgn(x - A.x) < 0 : sgn(y - A.y) > 0;
            return sgn(rs[id] - ls[A.id]) > 0;
        }
    };
    //u -> v;
    inline double Gslope(const node &u, const node &v) {
        return (v.y - u.y) / (v.x - u.x);
    }
    set<node > st;
    set<node >::iterator it, now, pre, nxt;
    void init(const double &x, const double &y) {
        st.insert((node){x, y, 1});
        ls[++cnt] = (1.0/0.0);
        rs[cnt] = -(1.0/0.0);
    }
    void insert(const double &x, const double &y) {
    	now = st.insert((node) {x, y, ++cnt}).first;
    	//如果有前驱获得前驱 
        if(now != st.begin()) it = now, --it, pre = it;
        ls[cnt] = (1.0/0.0), rs[cnt] = -(1.0/0.0);
        it = now, ++it, nxt = it;
        if(now != st.begin())
            ls[now -> id] = Gslope(*pre, *now);
        if(nxt != st.end()) 
            rs[now -> id] = Gslope(*now, *nxt);
        if(rs[now -> id] < ls[now -> id]) {
        	if(now != st.begin()) rs[pre -> id] = ls[now -> id];
            if(nxt != st.end()) ls[nxt -> id] = rs[now -> id];
        }
        else return st.erase(now), void();
        	
        if(now != st.begin())
            while(sgn(rs[pre -> id] - ls[pre -> id]) > 0) {
                it = pre, --pre;
                rs[pre -> id] = ls[now -> id] = Gslope(*pre, *now);
                st.erase(it);
            }
        if(nxt != st.end())
            while(sgn(rs[nxt -> id] - ls[nxt -> id]) > 0) {
                it = nxt, ++nxt;
                rs[now -> id] = ls[nxt -> id] = Gslope(*now, *nxt);
                st.erase(it);
            }
    }
    int GetK(double k) {
        rs[0] = ls[0] = k, D = 0;
        it = st.lower_bound((node) {0, 0, 0});
        return D = 1, it -> id;
    }
    #undef eps
}
int n; double S;
double f[maxn], a[maxn], b[maxn], R[maxn];
void ins(int i) {
    Convex::insert(R[i] * f[i] / (a[i] * R[i] + b[i]), 
                   f[i] / (a[i] * R[i] + b[i]));
}
int main() {
    //freopen("cash7.in", "r", stdin);
    using namespace Convex;
    scanf("%d%lf", &n, &S);
    for(register int i = 1; i <= n; ++i) {
        scanf("%lf%lf%lf", &a[i], &b[i], &R[i]);
    }
    f[1] = S;
    Convex::init(R[1] * f[1] / (a[1] * R[1] + b[1]), 
                f[1] / (a[1] * R[1] + b[1]));
    int v; double tmp;
    for(register int i = 2; i <= n; ++i) {
        v = Convex::GetK(-(a[i] / b[i]));
        tmp = f[v] / (a[v] * R[v] + b[v]);
        f[i] = max(tmp * R[v] * a[i] + tmp * b[i], f[i]);
        f[i] = max(f[i], f[i - 1]), ins(i);
    }
    printf("%.3lf", f[n]);
    return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链