【题目链接】
http://www.lydsy.com/JudgeOnline/problem.php?id=1492
【题意】
有AB两种货币，每天可以可以付IPi元，买到A券和B券，且A:B=Ratei，也可以卖掉OPi%的A券和B券，每天AB价值为Ai和Bi。
开始有S元，n天后手中不能有AB券，问最大获益。
【思路】
设f[i]表示前i天的最大收益。
第j天将手中的钱全部换掉，可以换成的B券数目Y(j)：f[j]*(1/(Rate[j]*A[j]+B[j]))
第j天将手中的钱全部换掉，可以换成的A券数目X(j)：f[j]*(Rate[j]/(Rate[j]*A[j]+B[j]))
第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)=-A[i]/B[i]*X(j)+p/B[j]的截距
设X(j)<X(k)，当k比j更优时需要满足slop(j,k)>-A[i]/B[i]
注意不能用单调队列维护因为x和斜率不是单调的。
我们需要维护一个上凸壳，可以使用splay（我不会=_=
考虑CDQ分治：
把每天看作一个点。将点按照-a/b升序排列。
定义sovle(l,r)为解决l,r内的所有询问，且保证solve结束后点按照x,y升序排列。
1.按照点的查询顺序分成[l,mid]与[mid+1,r]
2.递归处理左区间
3.此时左区间已经按照x,y排好序，扫一遍求出左区间的下凸线
4.计算左区间对右区间的影响。此时右区间按照-a/b升序排列，扫一遍更新右区间答案。
5.递归处理右区间
6.将区间按照x,y升序排列
【资源链接】
cdq论文->click here
【代码】
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; const int N = 1e5+;
const double inf = 1e20;
const double eps = 1e-; struct Pt {
double x,y,a,b,k,r;
int id;
bool operator < (const Pt& rhs) const {
return k>rhs.k;
}
}p[N],t[N]; double f[N];
int n,top,st[N]; double slop(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);
}
void solve(int l,int r)
{
if(l==r) {
f[l]=max(f[l],f[l-]);
p[l].y=f[l]/(p[l].a*p[l].r+p[l].b);
p[l].x=p[l].y*p[l].r;
return ;
}
int mid=(l+r)>>,j=,l1=l,l2=mid+;
for(int i=l;i<=r;i++) {
if(p[i].id<=mid) t[l1++]=p[i];
else t[l2++]=p[i];
}
for(int i=l;i<=r;i++) p[i]=t[i];
solve(l,mid);
top=;
for(int i=l;i<=mid;i++) {
while(top>&&slop(st[top-],st[top])<slop(st[top-],i)+eps) top--;
st[++top]=i;
}
st[++top]=;
for(int i=mid+;i<=r;i++) {
while(j<top&&slop(st[j],st[j+])+eps>p[i].k) j++;
f[p[i].id]=max(f[p[i].id],p[st[j]].x*p[i].a+p[st[j]].y*p[i].b);
}
solve(mid+,r);
l1=l,l2=mid+;
for(int i=l;i<=r;i++) {
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++];
}
for(int i=l;i<=r;i++) p[i]=t[i];
} int main()
{
scanf("%d%lf",&n,&f[]);
for(int i=;i<=n;i++) {
scanf("%lf%lf%lf",&p[i].a,&p[i].b,&p[i].r);
p[i].k=-p[i].a/p[i].b; p[i].id=i;
}
sort(p+,p+n+);
solve(,n);
printf("%.3lf",f[n]);
return ;
}