首先有一个显然的贪心，每次操作都要做到底，为了最优不会出现只卖一部分或者只买一部分的操作
所以设 $f[i]$ 表示前 $i$ 天得到的最大价值，那么对于每一个 $i$，枚举所有 $j<i$，意思就是第 $j$ 天全部买入，第 $i$ 天全部卖出
显然如果知道 $f[j]$，那么就知道第 $j$ 天买入多少
设 $A$ 买了 $X$， $B$ 买了 $Y$，那么 $f[i]=a[i]*X+b[i]*Y$
因为 $X,Y$ 只和 $j$ 有关，显然可以斜率优化
具体就是 $-a[i]*X+f[i]=b[i]*Y$，同除一个 $b[i]$，变成 $-a[i]/b[i]*X+f[i]/b[i]=Y$
那么 $k=-a[i]/b[i],x=X,b=f[i]/b[i],y=Y$
自己推一下，容易得出 $X_i=f[i]*r[i]/(a[i]*r[i]+b[i]),Y_i=f[i]/(a[i]*r[i]+b[i])$
然后因为 $k,x$ 都不单调，所以要用 $CDQ$ 搞
先按斜率排序，然后 $CQD$ 分治之前按下标拆成两部分，这个具体还是看代码吧...
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; typedef long long ll; typedef double db; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e5+7,INF=1e9+7; const db eps=1e-9; int n,S; db f[N]; struct dat{ db k,x,y,a,b,r; int id; inline bool operator < (const dat &tmp) const { return k<tmp.k; } }T[N],tmp[N]; inline db slope(int i,int j)//求斜率维护凸包 { if(fabs(T[i].x-T[j].x)<=eps) return T[i].y>T[j].y ? INF : -INF; return (T[i].y-T[j].y)/(T[i].x-T[j].x); } inline db Cross(db xa,db ya,db xb,db yb) { return xa*yb-xb*ya; }//用叉积维护凸包会更快 inline void merge(int l,int r,int mid)//按x归并排序 { int pl=l,pr=mid+1; for(int p=l;p<=r;p++) { if(pl<=mid&& (pr>r||T[pl].x<T[pr].x/*+eps*/) ) tmp[p]=T[pl++]; else tmp[p]=T[pr++]; } for(int p=l;p<=r;p++) T[p]=tmp[p]; } int Q[N];//栈，维护凸包 void CDQ(int l,int r) { if(l==r)//到了最底下，此时f[l]已经被所有f[j](j<l)更新完毕 { f[l]=max(f[l],f[l-1]);//这一天可以不操作 T[l].y=f[l]/(T[l].a*T[l].r+T[l].b),T[l].x=T[l].y*T[l].r; //更新f[l]完才求X[l],Y[l] return; } int mid=l+r>>1,pl=l,pr=mid+1,top=0; for(int p=l;p<=r;p++)//按下标分开 { if(T[p].id<=mid) tmp[pl++]=T[p]; else tmp[pr++]=T[p]; } for(int p=l;p<=r;p++) T[p]=tmp[p]; CDQ(l,mid); Q[0]=0;//先处理左边 for(int i=l;i<=mid;i++)//此时左边全部更新完毕，可以维护左边构成的凸包了 //注意此时左边的T[i].x是有序的,因为每次CDQ结束都会merge { while( top>1 && Cross(T[i].x-T[Q[top-1]].x,T[i].y-T[Q[top-1]].y,T[Q[top]].x-T[Q[top-1]].x,T[Q[top]].y-T[Q[top-1]].y)<=0 ) top--; Q[++top]=i; } for(int i=mid+1;i<=r;i++)//用左边构成的凸包更新右边,此时右边的斜率是有序的 { while( top>1 && /*T[i].k>=slope(Q[top-1],Q[top])+eps*/ //注释的内容和下一行是等价的,注意eps Cross(1,T[i].k,T[Q[top]].x-T[Q[top-1]].x,T[Q[top]].y-T[Q[top-1]].y)<=0 ) top--; int j=Q[top]; f[T[i].id]=max(f[T[i].id],T[j].x*T[i].a+T[j].y*T[i].b);//更新 } CDQ(mid+1,r); merge(l,r,mid);//处理右边后按x排序 } int main() { n=read(); f[0]=read(); for(int i=1;i<=n;i++) { scanf("%lf%lf%lf",&T[i].a,&T[i].b,&T[i].r); T[i].k=-T[i].a/T[i].b; T[i].id=i;//初始化 } sort(T+1,T+n+1); CDQ(1,n);//先按k排序再CDQ printf("%.3lf",f[n]); return 0; }