首先，最优情况一定是某一天把所有金券卖出或买入是最优的。
在金券一定的情况下，分散卖一定没有统一在最优的那天卖更优。
然后，我们假定在某一天卖，则在该天前面一定会有一天的全部买入能够使价值最大。
定义ans[i]为第i天能拥有的最大钱数。
则第i天能够有的A金券数为x[i]=ans[i]/(a[i]*rate[i]+b[i])*rate[i]，y[i]=ans[i]/(a[i]*rate[i]+b[i])。
ans[i]=max{x[j]*a[i]+y[j]*b[i],ans[i-1]}。(ans[i-1]是假如说该天最优是某一天往后的不买也不卖的情况，因为有时候并不是一定要买卖才是最优的。)
y[j]*b[i]=ans[i]-x[j]*a[i]
y[j]=x[j]*(-a[i]/b[i])+ans[i]/b[i]。
则我们要ans[i]最大，实际上就是在j<i的每一对(x[j],y[j])上画k=-a[i]/b[i]的直线，找最大的截距。这个一看就是凸包的套路。
但是关键是，(x[j],y[j])和直线k的斜率都是没有规律的（即没有递增或递减的情况），直接处理很麻烦。
我们考虑cdq分治。（一天为一个操作，一个操作里包含了该天的信息）
初始情况下，将所有的操作按斜率k来排序。当某一个子问题处理完毕后，将子问题内的所有操作按x坐标排序。这样，当我们分治处理时，[l,mid]内的所有操作都按x排序，[mid+1,r]内的所有操作都按斜率k排序了，当然也必须保证[l,mid]的操作顺序（即第几天）在[mid+1,r]之前。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const double eps=1e-9; int n; double ans[100010]; struct node{double a,b,k,rate,x,y;int id; }w[100010],q[100010]; int st[100010]; double K(int x,int y) {if (!y) return -1e20; if (fabs(w[x].x-w[y].x)<eps) return 1e20; return (w[y].y-w[x].y)/(w[y].x-w[x].x);} bool cmp1(node a,node b){return a.k<b.k;} bool cmp2(node a,node b) {return a.x<b.x;}//? void cdq(int l,int r) { if (l==r) { ans[l]=max(ans[l],ans[l-1]); w[l].y=ans[l]/(w[l].a*w[l].rate+w[l].b); w[l].x=w[l].y*w[l].rate; return; } int mid=(l+r)/2,js0=l,js1=mid+1,tp=0; for (int i=l;i<=r;i++) if (w[i].id<=mid) q[js0++]=w[i];else q[js1++]=w[i]; for (int i=l;i<=r;i++) w[i]=q[i]; cdq(l,mid); for (int i=l;i<=mid;i++) { while (tp>1&&K(st[tp],st[tp-1])<K(i,st[tp-1])+eps) tp--; st[++tp]=i; } int j=1; for (int i=mid+1;i<=r;i++) { while (tp>1&&w[i].k>K(st[tp],st[tp-1])-eps) tp--; ans[w[i].id]=max(ans[w[i].id],w[st[tp]].x*w[i].a+w[st[tp]].y*w[i].b); } cdq(mid+1,r);js0=l;js1=mid+1; merge(w+l,w+mid+1,w+mid+1,w+r+1,q+l,cmp2); for (int i=l;i<=r;i++) w[i]=q[i]; } int main() { scanf("%d%lf",&n,&ans[0]); for (int i=1;i<=n;i++) { scanf("%lf%lf%lf",&w[i].a,&w[i].b,&w[i].rate);w[i].id=i; w[i].k=-1.0*w[i].a/w[i].b; } sort(w+1,w+n+1,cmp1); cdq(1,n); printf("%.3f",ans[n]); }
[BZOJ1492]]NOI2007]cash-[cdq分治]
原文：https://www.cnblogs.com/coco-night/p/9536386.html