题目大意：太长了略
splay调了两天一直WA弃疗了
首先，我们可以猜一个贪心，如果买/卖，就一定都买/卖掉，否则不买/卖
反正货币的行情都是已知的，没有任何风险，所以肯定要选择最最最优的方案了
容易得到方程
$dp[i]=max(dp[i-1],a[i]*frac{dp[j]*rate[j]}{rate[j]*a[j]+b[j]}+b[i]*frac{dp[j]}{rate[j]*a[j]+b[j]})$
显然是要用凸优化了
splay非常无脑，splay维护此题的凸包，需要找前驱，删前驱，找后继，删后继，一大堆特判...绝对恶心到吐
所以这是一篇$CDQ$分治题解
令$x=frac{dp[j]}{rate[j]*a[j]+b[j]},y=x*rate[j]$
移项，可得
$dp[i]-b[i]*x=a[i]*y$
$y=frac{dp[i]}{a[i]}-frac{b[i]}{a[i]}x$
发现斜率$k=-frac{b[i]}{a[i]}$是一定的，我们在外层把斜率k从小到大排序，可以优化掉一个$log$，递归时按$x$从小到大排序
这样，递归时，每一层内部都是按$k$有序的，把这一层按照时间分为左右两个部分(不要破坏$k$的有序状态)
先递归处理左半个区间，回溯后，左半部分的答案已知，且不会被右半部分的答案所影响
且左半部分按$x$从小到大排序，右半部分按斜率$k$从小到大排序，取最小值，由于$k<0$，用单调栈维护一个上凸包即可
处理完了左边对右边的贡献，递归处理右半部分
回溯时，先处理$dp[i]=dp[i-1]$的情况，再按$x$排序，回溯到上一层
1 #include <cmath> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #define N1 101000 6 #define M1 205 7 #define ll long long 8 #define dd double 9 #define uint unsigned int 10 #define inf 233333333 11 #define il inline 12 using namespace std; 13 14 const dd eps=(1e-9); 15 int n,m; 16 int stk[N1]; 17 dd A[N1],B[N1],r[N1],X[N1],Y[N1],K[N1],f[N1]; 18 //struct node{dd x,y,k,ans;int id;}; 19 int cmp1(int s1,int s2){return K[s1]-K[s2]<0;} 20 int id[N1],tmp[N1]; 21 dd get_slope(int s1,int s2){ 22 if(!s2) return inf; 23 return (Y[s1]-Y[s2])/(X[s1]-X[s2]); 24 } 25 void CDQ(int L,int R) 26 { 27 if(R-L<=1) return; 28 int M=(L+R)>>1; 29 int tp=0,i,j,pl=L,pr=M,k,cnt; 30 for(int i=L;i<R;i++) 31 if(id[i]<M) tmp[pl++]=id[i]; 32 else tmp[pr++]=id[i]; 33 for(int i=L;i<R;i++) 34 id[i]=tmp[i]; 35 CDQ(L,M); 36 for(i=L;i<M;i++) 37 { 38 k=id[i]; 39 if(tp>1&&fabs(X[stk[tp]]-X[k])<eps&&Y[k]-Y[stk[tp]]<eps) continue; 40 while(tp>1&&get_slope(stk[tp],stk[tp-1])<=get_slope(k,stk[tp-1])) 41 tp--; 42 stk[++tp]=k; 43 } 44 for(i=M;i<R;i++) 45 f[i]=max(f[i-1],f[i]); 46 for(i=M;i<R;i++) 47 { 48 while(tp>1&&get_slope(stk[tp],stk[tp-1])<=K[id[i]]) 49 tp--; 50 k=id[i],j=stk[tp]; 51 f[k]=max(f[k],A[k]*Y[j]+B[k]*X[j]); 52 X[k]=f[k]/(A[k]*r[k]+B[k]); 53 Y[k]=r[k]*X[k]; 54 } 55 CDQ(M,R); 56 i=L,cnt=L,j=M; 57 while(i<M&&j<R){ 58 if(X[id[i]]<X[id[j]]) 59 tmp[cnt++]=id[i],i++; 60 else 61 tmp[cnt++]=id[j],j++; 62 } 63 while(i<M) tmp[cnt++]=id[i],i++; 64 while(j<R) tmp[cnt++]=id[j],j++; 65 for(i=L;i<R;i++) 66 id[i]=tmp[i],f[id[i]]=max(f[id[i]],f[id[i]-1]); 67 }; 68 dd S; 69 int main() 70 { 71 //freopen("t1.in","r",stdin); 72 scanf("%d%lf",&n,&S); 73 for(int i=1;i<=n;i++) 74 { 75 scanf("%lf%lf%lf",&A[i],&B[i],&r[i]); 76 K[i]=-B[i]/A[i];id[i]=i; 77 } 78 f[1]=S,X[1]=S/(A[1]*r[1]+B[1]),Y[1]=X[1]*r[1]; 79 sort(id+1,id+n+1,cmp1); 80 CDQ(1,n+1); 81 dd ans=0; 82 for(int i=1;i<=n;i++) 83 ans=max(ans,f[i]); 84 printf("%.3lf ",ans); 85 return 0; 86 }