題目
先來畫一畫柿子
設\(dp_i\)表示你第\(i\)天之后最多剩下多少錢
考慮一下對于\(i\)的轉移，我們肯定要在之前枚舉一天\(j\)這一天把所有的東西買進來，之后在\(i\)天賣掉
設那天買進\(A\)的量為\(d_a\)，買進\(B\)的量為\(d_b\)
我們可以得到這樣的方程
\[d_ap_a+d_bp_b=dp_j\]
\[d_a:d_b=R_j:1\]
來愉快的解方程吧
\[d_a=d_bR_j\]
\[R_jd_bp_a+d_bp_b=dp_j\]
\[d_b(R_jp_a+p_b)=dp_j\]
\[d_b=\frac{dp_j}{R_jp_a+p_b}\]
\[d_a=\frac{dp_jR_j}{R_jp_a+p_b}\]
那么我們從\(i\)天賣出收益就是
\[dp_i=p_{a,i}\frac{dp_jR_j}{R_jp_{a,j}+p_{b,j}}+p_{b,i}\frac{dp_j}{R_jp_{a,j}+p_{b,j}}\]
那就是求一個點積最大值啊
考慮凸殼來優化
\[dp_i=p_ad_a+p_bd_b\]
\[\frac{dp_i}{p_b}=\frac{p_a}{p_b}d_a+d_b\]
\[-\frac{p_a}{p_b}d_a+\frac{dp_i}{p_b}=d_b\]
斜率為\(-\frac{p_a}{p_b}\)的直線去卡凸殼上的點，最大化一個截距就好了
由于什么也不單調，選擇用\(CDQ\)分治來維護這個\(dp\)
代碼
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
# include <cmath>
#define maxn 100005
#define re register
#define LL long long
#define double double
#define eps 1e-10
#define max(a,b) ((a)>(b)?(a):(b))
int n,h=1,t,q[maxn];
double pa[maxn],pb[maxn],ra[maxn];
struct Node{int rk;double x,y;}a[maxn];
double dp[maxn],X[maxn],Y[maxn];
inline int cmp(Node A,Node B) {return A.x<B.x;}
inline int cop(Node A,Node B) {return A.rk<B.rk;}
inline int check(double x,double y) {if(fabs(x-y)<eps) return 1;return 0;}
inline int K(int e,int f,int g,int h) {if(check(X[g],X[h])&&check(X[f],X[e])) return Y[h]-Y[g]>Y[f]-Y[e]+eps;if(check(X[g],X[h])) return Y[h]-Y[g]>-eps;if(check(X[e],X[f])) return Y[e]-Y[f]<eps;double a1=Y[f]-Y[e],a2=Y[h]-Y[g];double b1=X[f]-X[e],b2=X[h]-X[g];return b2*a1-eps<a2*b1;
}
inline int KK(int e,int f,double a2,double b2) {double a1=Y[f]-Y[e],b1=X[f]-X[e];return b2*a1+eps<a2*b1;
}
inline void ins(int x) {while(h<t&&K(q[t-1],q[t],q[t-1],x)) --t;q[++t]=x;
}
inline int find(double a2,double b2)
{if(h==t) return q[t];if(h==t-1) {if(KK(q[h],q[t],a2,b2)) return q[h];return q[t];}int l=h,r=t;while(l<=r) {if(l==r-1) {if(KK(q[l],q[r],a2,b2)) return q[l];return q[r];}int mid=l+r>>1;if(mid+1>r) break;if(KK(q[mid],q[mid+1],a2,b2)) r=mid;else l=mid+1;}return q[l];
}
void CDQ(int l,int r) {if(l==r) {dp[l]=max(dp[l-1],dp[l]);a[l].y=Y[l]=dp[l]/(ra[l]*pa[l]+pb[l]);a[l].x=X[l]=Y[l]*ra[l];return;}int mid=l+r>>1;CDQ(l,mid);std::sort(a+l,a+mid+1,cmp);h=1,t=0;for(re int i=l;i<=mid;i++) ins(a[i].rk);for(re int i=mid+1;i<=r;i++) {int x=find(-1.0*pa[i],pb[i]);dp[i]=max(pa[i]*X[x]+pb[i]*Y[x],dp[i]);}CDQ(mid+1,r);
}
int main()
{scanf("%d",&n);double T;scanf("%lf",&T);dp[1]=T;for(re int i=1;i<=n;i++) {scanf("%lf",&T);pa[i]=T;scanf("%lf",&T);pb[i]=T;scanf("%lf",&T);ra[i]=T;}for(re int i=1;i<=n;i++) a[i].rk=i;CDQ(1,n);printf("%.3lf\n",(double)dp[n]);return 0;
}
)
