Description
小 Y 最近在一家金券交易所工作。该金券交易所只发行交易两种金券：A 纪念券（以下简称 A 券）和 B 纪念券（以下简称 B 券）。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。
每天随着市场的起伏波动，两种金券都有自己当时的价值，即每一单位金券当天可以兑换的人民币数目。我们记录第 $K$ 天中 A 券和 B 券的价值分别为 $A_K$ 和 $B_K$ （元/单位金券）。
为了方便顾客，金券交易所提供了一种非常方便的交易方式：比例交易法。
比例交易法分为两个方面：
a) 卖出金券：顾客提供一个 $[0，100]$ 内的实数 $OP$ 作为卖出比例，其意义为：将 $OP\%$ 的 A 券和 $OP\%$ 的 B 券以当时的价值兑换为人民币；
b) 买入金券：顾客支付 $IP$ 元人民币，交易所将会兑换给用户总价值为 $IP$ 的金券，并且，满足提供给顾客的 A 券和 B 券的比例在第 $K$ 天恰好为 $mathrm{Rate}_ K$；
例如，假定接下来 $3$ 天内的 $A_K,B_K,mathrm{Rate}_ K$ 的变化分别为：
| 时间 | $A_K$ | $B_K$ | $mathrm{Rate}_ K$ |
| ----- | ----- | ----- | ----- |
| 第一天 | $1$ | $1$ | $1$ |
| 第二天 | $1$ | $2$ | $2$ |
| 第三天 | $2$ | $2$ | $3$ |
假定在第一天时，用户手中有 $100$ 元人民币但是没有任何金券。
用户可以执行以下的操作：
| 时间 | 用户操作 | 人民币(元) | A 券的数量 | B 券的数量 |
| ----- | ----- | ----- | ----- | ----- |
| 开户 | 无 | $100$ | $0$ | $0$ |
| 第一天 | 买入 $100$ 元 | $0$ | $50$ | $50$ |
| 第二天 | 卖出 $50\%$ | $75$ | $25$ | $25$ |
| 第二天 | 买入 $60$ 元 | $15$ | $55$ | $40$ |
| 第三天 | 卖出 $100\%$ | $205$ | $0$ | $0$ |
注意到，同一天内可以进行多次操作。
小 Y 是一个很有经济头脑的员工，通过较长时间的运作和行情测算，他已经知道了未来 $N$ 天内的 A 券和 B 券的价值以及 $mathrm{Rate}$。他还希望能够计算出来，如果开始时拥有 $S$ 元钱，那么 $N$ 天后最多能够获得多少元钱。
Solution
设$f_i$表示第$i$天持有钱数，并且知道最优方案一定是某一天将钱花光，之后全部卖出
egin{cases}
xA_i+yB_i = f_i \
frac{x}{y}=R_i
end{cases}
解得
$$y_i=frac{f_i}{A_iR_i+B_i} ,x_i=frac{R_if_i}{A_iR_i+B_i} $$
假设现在更新$f_j$，有$f_j=max{x_iA_j+y_iB_j}$
解得$y_i=-frac{A_j}{B_j}x_i+frac{f_j}{B_j} $
要求最大化截距，CDQ分治过程中维护上凸壳，CDQ右区间按斜率排序，左区间按照横坐标排序，所以查询时是有序的
时间复杂度$O(n log n)$
#include<algorithm> #include<iostream> #include<cstdio> #include<cmath> using namespace std; int n,sta[100005]; const int inf=0x7f7f7f7f; double dp[100005]; struct Node{ double A,B,R,k,id,x,y; bool operator <(const Node &z)const{return k<z.k;} }node[100005],temp[100005]; inline int read(){ int f=1,w=0; char ch=0; while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=getchar(); return f*w; } double slope(int i,int j){ if(node[i].x==node[j].x)return inf; return (node[j].y-node[i].y)/(node[j].x-node[i].x); } void merge(int l,int r){ int mid=l+r>>1,t1=l,t2=mid+1; for(int i=l;i<=r;i++) if(t1<=mid&&(t2>r||node[t1].x<=node[t2].x))temp[i]=node[t1++]; else temp[i]=node[t2++]; for(int i=l;i<=r;i++)node[i]=temp[i]; } void CDQ(int l,int r){ if(l==r){dp[l]=max(dp[l],dp[l-1]),node[l].y=dp[l]/(node[l].A*node[l].R+node[l].B),node[l].x=node[l].R*node[l].y;return;} int mid=l+r>>1,t1=l-1,t2=mid,top=0; for(int i=l;i<=r;i++) if(node[i].id<=mid)temp[++t1]=node[i]; else temp[++t2]=node[i]; for(int i=l;i<=r;i++)node[i]=temp[i]; CDQ(l,mid); for(int i=l;i<=mid;i++){ while(top>=2&&slope(sta[top],i)>=slope(sta[top-1],sta[top]))--top; sta[++top]=i; } for(int i=mid+1;i<=r;i++){ while(top>=2&&slope(sta[top-1],sta[top])<=node[i].k)--top; dp[(int)node[i].id]=max(dp[(int)node[i].id],node[sta[top]].x*node[i].A+node[sta[top]].y*node[i].B); } CDQ(mid+1,r),merge(l,r); } int main(){ n=read(),dp[0]=read(); for(int i=1;i<=n;i++)scanf("%lf%lf%lf",&node[i].A,&node[i].B,&node[i].R),node[i].k=-node[i].A/node[i].B,node[i].id=i; sort(node+1,node+n+1),CDQ(1,n),printf("%.3lf ",dp[n]); return 0; }