设 $f_i$ 表示第 $i$ 天最大的收益。
初始条件 $f_0=s$，答案 $f_n$。
转移枚举上一个全买券的点 $j$，设 $y$ 表示第 $j$ 天买 $B$ 的数量，解方程。
$Rate_j\times y_j\times a_j+y_j\times b_j=f_j$
得到 $y_j=\large\frac{f_j}{Rate_j\times a_j+b_j}$
设 $x$ 表示买 $A$ 的数量，显然 $x_i=Rate_j\times y_i$
转移方程 $f_i=\max(f_{i-1},\max{a_i\times x_j+b_i\times y_j | j\in[1,i) } )$
提出 $b_i$，得到 $f_i=\max(f_{i-1},b_i\times \max{\large\frac{a_i}{b_i}\small\times x_j+y_j})$
发现变成一次函数形式，即对于每个 $x_j,y_j$，查询 $\large\frac{a_i}{b_i}$ 处的最大值即可。
李超线段树即可（这里是一个简洁的李超树板子 qwq）。
#include<bits/stdc++.h>
using namespace std;
#define db double
#define endl '\n'
const int N=1e5+10;
int n;
db s;
db x[N],y[N],k[N],c[N];
db f[N],a[N],b[N],r[N];
int t[N<<2];
db calc(int i,int p){return x[i]*k[p]+y[i];}
void update(int p,int l,int r,int x){
if(l==r){
if(calc(t[p],l)<calc(x,l)) t[p]=x;
return ;
}
int mid=(l+r)>>1;
if(calc(t[p],mid)<calc(x,mid)) swap(t[p],x);
if(calc(t[p],l)<calc(x,l)) update(p<<1,l,mid,x);
else update(p<<1|1,mid+1,r,x);
}
db query(int p,int l,int r,int x){
if(l==r) return calc(t[p],x);
int mid=(l+r)>>1;
db res=calc(t[p],x);
if(x<=mid) return max(res,query(p<<1,l,mid,x));
return max(res,query(p<<1|1,mid+1,r,x));
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>s;
f[0]=s;
for(int i=1;i<=n;++i){
cin>>a[i]>>b[i]>>r[i];
k[i]=c[i]=a[i]/b[i];
}
sort(k+1,k+1+n);
for(int i=1;i<=n;++i){
int u=lower_bound(k+1,k+1+n,c[i])-k;
f[i]=max(f[i-1],b[i]*query(1,1,n,u));
db p=a[i]*r[i]+b[i];
y[i]=f[i]/p;
x[i]=y[i]*r[i];
update(1,1,n,i);
}
cout<<fixed<<setprecision(3)<<f[n]<<endl;
return 0;
}
|
