标签：CDQ分治，凸包，DP
题目
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、BK、RateK，意义如题目中所述。
对于100%的测试数据，满足：0<AK≤10；0<BK≤10；0<RateK≤100；MaxProfit≤1 0^9。
Output
只有一个实数MaxProfit，表示第N天的操作结束时能够获得的最大的金钱数目。答案保留3位小数。
Sample Input
3 100
1 1 1
1 2 2
2 2 3
Sample Output
225.000
HINT
- 输入文件可能很大，请采用快速的读入方式。
- 必然存在一种最优的买卖方案满足： 每次买进操作使用完所有的人民币； 每次卖出操作卖出所有的金券。
题意
有AB两种货币，每天可以可以付Pi元，买到A券和B券，且A:B=Ratei，也可以卖掉OPi%的A券和B券，每天AB价值为Ai和Bi。开始有S元，n天后手中不能有AB券，问最大获益。
分析
显示O(n^2)DP
设f[i]表示前i天的最大收益
第i天将手中的钱全部换掉，可以换成的A券数目X(i)：\(f[i] * \frac {Rate[i]} {Rate[i] * A[i]+B[i]}\)
第i天将手中的钱全部换掉，可以换成的B券数目Y(i)：\(f[i] * \frac 1 {Rate[i] * A[i]+B[i]}\)
第i天将第j天的AB券全部卖掉：\(A[i] * X(j)+B[i] * Y(j)\)
则状态转移方程为 \(f[i]=max( f[i-1],A[i]*X(j)+B[i]*Y(j) )\)
那么我们需要求 \(max(p=A[i]*X(j)+B[i]*Y(j))\)
转化为直线方程\(Y(j)=-\frac {A[i]} {B[i]} * X(j)+\frac p {B[i]}\)
使这条直线的截距最大
设X(j) < X(k)，当k比j更优时需要满足\(slop(j,k)>-\frac {A[i]}{B[i]}\)
因为X(i)可能不是单调的，所以不能够用单调队列来维护，我们这里需要维护一个凸壳
然后就用到了CDQ分治（第一次写，膜了黄学长代码qwq）
CDQ分治大题思想就是进行左区间的分治时考虑对右区间的影响
按照时间轴分治，把每天看成一个点，首先将所有点按照斜率排序
并且保证操作结束后按照x,y升序排列
具体步骤代码里有详细注释
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define inf 1e9
#define eps 1e-6
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1e5+6;
int n,top,stack[maxn];double f[maxn];
struct point{double x,y,a,b,k,rate;int w,id;}p[maxn],t[maxn];
inline double getk(int a,int b){
if(!b)return -inf;
if(fabs(p[a].x-p[b].x)<eps)return inf;
return (p[b].y-p[a].y)/(p[b].x-p[a].x);
}//用于维护凸壳
inline bool operator < (point a,point b){return a.k>b.k;}
void solve(int l,int r){
if(l==r){
f[l]=max(f[l],f[l-1]);
p[l].y=f[l]/(p[l].a*p[l].rate+p[l].b);
p[l].x=p[l].rate*p[l].y;
return;
}//分治结束直接计算结果
int l1=l,mid=(l+r)>>1,l2=mid+1,j=1;
rep(i,l,r)
if(p[i].id<=mid)t[l1++]=p[i];else t[l2++]=p[i];
rep(i,l,r)p[i]=t[i];//将原顺序分为左右两块
solve(l,mid);//递归处理左区间
top=0;
rep(i,l,mid){
while(top>1&&getk(stack[top-1],stack[top])<getk(stack[top-1],i)+eps)top--;
stack[++top]=i;
}//扫一遍求出左区间的下凸线
stack[++top]=0;
rep(i,mid+1,r){
while(j<top&&getk(stack[j],stack[j+1])+eps>p[i].k)j++;
f[p[i].id]=max(f[p[i].id],p[stack[j]].x*p[i].a+p[stack[j]].y*p[i].b);
}//计算左区间对右区间的影响，扫一遍更新右区间答案
solve(mid+1,r);//递归处理右区间
l1=l;l2=mid+1;
rep(i,l,r)
if(((p[l1].x<p[l2].x||(fabs(p[l1].x-p[l2].x)<eps&&p[l1].y<p[l2].y))||l2>r)&&l1<=mid)t[i]=p[l1++];
else t[i]=p[l2++];
rep(i,l,r)p[i]=t[i];//将区间按照x,y升序排列
}
int main()
{
scanf("%d%lf",&n,&f[0]);
rep(i,1,n){
scanf("%lf%lf%lf",&p[i].a,&p[i].b,&p[i].rate);
p[i].k=-p[i].a/p[i].b;p[i].id=i;
}
sort(p+1,p+1+n);//按斜率进行排序
solve(1,n);
printf("%.3lf\n",f[n]);
return 0;
}
