Description
Link.
一共 $n$ 天，每天可以卖出或者买入两种股票 $A$ 和 $B$。这两种股票在第 $i$ 天的价值为 $A_i$ 和 $B_i$。
每天可以花所有的现金买入股票，这些股票中 $A$ 股与 $B$ 股的数量比为 $rate_i$。每天也可以把所有的股票以当天的价值卖出，获得现金。已知接下来 $n$ 天的 $A_i,B_i,rate_i$，求出 $n$ 天后能够获得的最大价值。
Solution
设 $f(i)$ 为第 $i$ 天的最大钱数，$g_{1}(i)$ 为 A 券的第 $i$ 天能换的数量，$g_{2}(i)$ 则为 B 券。
转移可以解方程得：
$$ f(i)=\max\{f(i-1),a(i)g_{1}(j),b(i)g_{2}(j)\},j\in[1,i) \\ g_{1}(i)\frac{f(i)rate(i)}{a(i)rate(i)+b(i)} \\ g_{2}(i)=\frac{f(i)}{rate(i)\times a(i)+b(i)} \\ $$
两个 $g$ 都没啥问题，主要来看 $f(i)$。提一下可得：
$$ f(i)=\max\{b(i)\max_{j=1}^{i-1}\{\frac{a(i)}{b(i)}g_{1}(j)+g_{2}(j)\},f(i-1)\} $$
斜率优化的形式，但斜率并无单调性。那个 $f(i-1)$ 可以最后来线性做，所以可以先不管。然后就是 li-chao tree 的板子。
#include<bits/stdc++.h>
std::vector<double> pri;
int n,nodes[400010];
double g[5][100010],f[100010],a[100010],b[100010],rate[100010],slp[100010];
double _f(int i,int j){return pri[i-1]*g[1][j]+g[2][j];}
void ins(int l,int r,int x,int i)
{
if(l^r)
{
int mid=(l+r)>>1;
if(_f(mid,i)>_f(mid,nodes[x])) std::swap(nodes[x],i);
if(_f(l,i)>_f(l,nodes[x])) ins(l,mid,x<<1,i);
else ins(mid+1,r,x<<1|1,i);
}
else if(_f(l,i)>_f(l,nodes[x])) nodes[x]=i;
}
double find(int l,int r,int x,int i)
{
if(l^r)
{
int mid=(l+r)>>1;
if(mid>=i) return std::max(find(l,mid,x<<1,i),_f(i,nodes[x]));
else return std::max(find(mid+1,r,x<<1|1,i),_f(i,nodes[x]));
}
else return _f(i,nodes[x]);
}
#define All(x) (x).begin(),(x).end()
int main()
{
double pref=0,nowf=0;
scanf("%d %lf",&n,&nowf);
pref=nowf;
for(int i=1;i<=n;++i)
{
scanf("%lf %lf %lf",&a[i],&b[i],&rate[i]);
slp[i]=a[i]/b[i];
pri.emplace_back(slp[i]);
}
std::sort(All(pri));
for(int i=1;i<=n;++i)
{
nowf=std::max(pref,b[i]*find(1,n,1,std::lower_bound(All(pri),slp[i])-pri.begin()+1));
g[1][i]=nowf*rate[i]/(a[i]*rate[i]+b[i]);
g[2][i]=nowf/(a[i]*rate[i]+b[i]);
ins(1,n,1,i);
pref=nowf;
}
printf("%.3f\n",nowf);
return 0;
}