dp[i] 表示 第i天卖完的最大收益

朴素的dp：

枚举从哪一天买来的在第i天卖掉,或者是不操作

dp[i]=max(dp[i-1],X[j]*A[i]+Y[j]*B[i])

其中X[j]表示在第j天能买多少A纪念券，Y[j]表示在第j天能买多少B纪念券

可列方程 X[j]*A[j]+Y[j]*B[j]=dp[j]

又因为 X[j]=Rate[j]*Y[j]

所以解出 Y[j]=dp[j]/(B[j]+A[j]*Rate[j])

 

优化：

dp[i]=X[j]*A[i]+Y[j]*B[i]

Y[j]=dp[i]/B[i] - A[i]/B[i] * x[j]

斜率优化形式，维护上凸壳，最大化截距

点：（X[j]，Y[j]）

斜率：-A[i]/B[i]

但是 -A[i]/B[i] 不具有单调性

所以不能用单调队列维护斜率

可以用平衡树维护，O（n * logn * logn）

更简单的方法：CDQ分治

 

假设现在正在计算 dp[l]~dp[r]，即solve（l，r）

对于每个j∈[l,r]，[1,j-1]都是j的一种决策

令 mid=（l+r）/ 2

我们先计算出 dp[l]~dp[mid]，然后用这些去更新 dp[mid+1]~dp[r]

假设我们现在已有了dp[l]~dp[mid]的上凸壳

那么如果保证 mid+1~r的斜率单调

就可以在线性时间内完成 dp[l]~dp[mid] 对 dp[mid+1]~dp[r]的更新

斜率单调可以在归并排序之前的排序预处理中解决

仅剩的问题：如何得到dp[l]~dp[mid] 构成的上凸壳？

在每一层最后归并的时候，我们用线形的时间使l~mid 的点 有序

即横坐标为第一关键字，纵坐标为第二关键字 升序排列，

那么处理完l~mid之后，

会得到l~mid 所有的点 升序排列的结果

对于一些有序的点，用单调栈维护斜率递减即可维护出上凸壳

然后利用这个上凸壳去更新mid+1~r 即可

复杂度为 O(nlogn)

 

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define N 100001const double eps=1e-7;struct node{    double A,B,R;    double X,Y;    double K;    int id;        bool operator < (node p) const    {        /*if(fabs(X-p.X)>eps)  return X
         
          >1;    int opl=l,opr=mid+1;    for(int i=l;i<=r;++i)        if(e[i].id<=mid) t[opl++]=e[i];        else t[opr++]=e[i];    for(int i=l;i<=r;++i) e[i]=t[i];    solve(l,mid);    top=0;    for(int i=l;i<=mid;++i)    {        while(top>1 && !down(st[top-1],st[top],i)) top--;        st[++top]=i;    }    int now=1;    for(int i=mid+1;i<=r;++i)    {        while(now
          
           mid) t[i]=e[opr++]; else if(opr>r) t[i]=e[opl++]; else if(e[opl]
           
            q.K;}int main(){ int n; double m; scanf("%d%lf",&n,&dp[0]); for(int i=1;i<=n;++i) { scanf("%lf%lf%lf",&e[i].A,&e[i].B,&e[i].R); e[i].K=-e[i].A/e[i].B; e[i].id=i; } sort(e+1,e+n+1,cmp); solve(1,n); printf("%.3lf",dp[n]);}
           
          
         
        
       
      
     

 

1492: [NOI2007]货币兑换Cash

Time Limit: 5 Sec  Memory Limit: 64 MB

Submit: 5830  Solved: 2342

[][][]

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