题意：不想写...
好吧我回来了
首先发现每次兑换一定是全部兑换，因为你兑换说明有利可图，是为了后面的某一天两种卷的汇率差别明显而兑换
那么一定拿全利啊，一定比多天的组合好
$f[i]$表示第$i$天最多能得到的钱在这一天可以换成多少$A$卷
枚举使用哪一天留下的卷，按这一天的汇率换成钱来更新最大钱数
再用这个钱数更新$f[i]$
这样是$O(n^2)$的
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
const int N=1e5+,M=1e4+;
const double eps=1e-;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,s;
double a[N],b[N],r[N];
double f[N];
void dp(){
f[]=s*r[]/(a[]*r[]+b[]);
double t=s;
for(int i=;i<=n;i++){
for(int j=;j<i;j++) t=max(t,f[j]*a[i]+f[j]/r[j]*b[i]);
f[i]=max(f[i],t*r[i]/(a[i]*r[i]+b[i]));
}
printf("%.3lf",t);
}
int main(){
freopen("in","r",stdin);
n=read();s=read();
for(int i=;i<=n;i++) scanf("%lf%lf%lf",&a[i],&b[i],&r[i]);
dp();
}
DP-naive
然后发现这个式子可以斜率优化
假设转移$j$比$k$更优，且$f_j<f_k$
令$g_i=\frac{f_i}{r_i}$
$\frac{g_k-g_j}{f_k-f_j}\ <\ -\frac{a_i}{b_i}$
然后$f$不单调，所以用平衡树或者CDQ分治来维护
$CDQ$分治里左面按$x$排序，右面按$k$排序
注意：
CDQ分治中$l$和$1$一定别打错.........我$Debug$了好长时间
比较斜率的时候要$+eps$，精度太玄学了呜呜呜
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=1e5+;
const double eps=1e-;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n;
double d[N];
struct Day{
double a,b,r,k,x,y;
int id;
bool operator <(const Day &r)const{return k>r.k;}
}p[N],t[N];
inline bool cmp(Day &a,Day &b){//a<b
return a.x<b.x||(abs(a.x-b.x)<eps&&a.y<b.y);
}
inline double slope(int a,int b){
if(abs(p[a].x-p[b].x)<eps) return 1e20;
else return (p[a].y-p[b].y)/(p[a].x-p[b].x);
}
int st[N],top;
void Solve(int l,int r){//printf("Solve %d %d\n",l,r);
if(l==r){
d[l]=max(d[l],d[l-]);
p[l].y=d[l]/(p[l].a*p[l].r+p[l].b);
p[l].x=p[l].y*p[l].r;
return;
}
int mid=(l+r)>>,p1=l,p2=mid+;
for(int i=l;i<=r;i++){
if(p[i].id<=mid) t[p1++]=p[i];
else t[p2++]=p[i];
}
for(int i=l;i<=r;i++) p[i]=t[i]; Solve(l,mid);
top=;
for(int i=l;i<=mid;i++){
while(top>&&slope(st[top-],st[top])<slope(st[top-],i)+eps) top--;
st[++top]=i;//printf("st %d\n",i);
}
//
int j=;
for(int i=mid+;i<=r;i++){
while(j<top&&slope(st[j],st[j+])+eps>p[i].k) j++;
d[p[i].id]=max(d[p[i].id],p[st[j]].x*p[i].a+p[st[j]].y*p[i].b);
}
Solve(mid+,r);
p1=l;p2=mid+;
for(int i=l;i<=r;i++){
if(p1<=mid&&( p2>r||cmp(p[p1],p[p2]) )) t[i]=p[p1++];
else t[i]=p[p2++];
}
for(int i=l;i<=r;i++) p[i]=t[i];
}
int main(){
//freopen("in","r",stdin);
freopen("cash.in","r",stdin);
freopen("cash.out","w",stdout);
n=read();d[]=read();
for(int i=;i<=n;i++)
scanf("%lf%lf%lf",&p[i].a,&p[i].b,&p[i].r),
p[i].k=-p[i].a/p[i].b,p[i].id=i;
sort(p+,p++n);
Solve(,n);
//for(int i=1;i<=n;i++) printf("hi %d %d %lf\n",i,p[i].id,d[i]);
printf("%.3lf",d[n]);
return ;
}