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 的变化分别为：

注意到，同一天内可以进行多次操作。小Y是一个很有经济头脑的员工，通过较长时间的运作和行情测算，他已经

知道了未来N天内的A券和B券的价值以及Rate。他还希望能够计算出来，如果开始时拥有S元钱，那么N天后最多能

够获得多少元钱。

solution

正解：CDQ+斜率优化DP

DP基于一个贪心思想：如果要买入或者卖出，一定是买完或卖完，所以当天所持有的A,B劵的数量已经确定了，设为 \(x[i],y[i]\)

\(y[i]=f[i]/(a[i]*rate[i]+b[i]),x[i]=y[i]*rate[i]\)

\(f[i]=max(f[i],a[i]*x[j]+b[i]*y[j])\)

变形 \(y[j]=-a[i]/b[i]*x[j]+f[i]/b[i]\)

那么就变成了一条直线，要使得\(f[i]\)大，就得让截距尽量大，维护上凸壳即可，答案一定是在斜率为\(-a[i]/b[i]\)的直线与凸包相切时，按斜率排序，单调指针扫描即可

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define RG register#define il inline#define iter iterator#define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)<(b)?(a):(b))using namespace std;typedef long long ll;const int N=100005;const double inf=2e8,eps=1e-7;int n;double f[N],rate[N],a[N],b[N];struct node{ double k;int id;}q[N];bool compid(node i,node j){return i.id
          
           j.k;}struct Point{double x,y;}p[N];bool comp(Point i,Point j){ if(i.x!=j.x)return i.x
           
            >1; sort(q+l,q+r+1,compid); solve(l,mid); sort(q+mid+1,q+r+1,compk); top=0; for(RG int i=l;i<=mid;i++){ while(top>=2 && k(i,st[top])>k(st[top],st[top-1]))top--; st[++top]=i; } int j=1; for(RG int i=mid+1;i<=r;i++){ while(j