题意略
题解:可以列出dp方程\(dp[i]=max(dp[j]*{\frac{a[i]*c[j]+b[i]}{a[j]*c[j]+b[j]}}\),化简可以得到\(\frac{dp[i]}{b[i]}=\frac{a[i]}{b[i]}*\frac{dp[j]*c[j]}{a[j]*c[j]+b[j]}+\frac{dp[j]}{a[j]*c[j]+b[j]}\),就变成了y=kx+b的形式,能cdq分治维护,也能set维护动态凸包
cdq:
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize(4)
//#pragma GCC optimize("unroll-loops")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define fi first
#define se second
#define db double
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define vi vector<int>
#define mod 1000000007
#define ld long double
//#define C 0.5772156649
//#define ls l,m,rt<<1
//#define rs m+1,r,rt<<1|1
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pii pair<int,int>
#define ull unsigned long long
//#define base 1000000000000000000
#define fin freopen("a.txt","r",stdin)
#define fout freopen("a.txt","w",stdout)
#define fio ios::sync_with_stdio(false);cin.tie(0)
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}
inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}
template<typename T>inline T const& MAX(T const &a,T const &b){return a>b?a:b;}
template<typename T>inline T const& MIN(T const &a,T const &b){return a<b?a:b;}
inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c,b>>=1;}return ans;}
using namespace std;
const ull ba=233;
const db eps=1e-5;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int N=100000+10,maxn=100000+10,inf=0x3f3f3f3f;
ld a[N],b[N],c[N],dp[N];
struct info{
ld x,y;int id;
bool operator <(const info&rhs)const{
return x<rhs.x||(x==rhs.x&&y<rhs.y);
}
}d[N];
struct hull{
int head,last,q[N];
void init(){head=1,last=0;}
ld X(int i){return dp[i]*c[i]/(a[i]*c[i]+b[i]);}
ld Y(int i){return dp[i]/(a[i]*c[i]+b[i]);}
ld cal(int i,ld k){return Y(i)-k*X(i);}
bool check(int a,int b,int c)
{
return (Y(b)-Y(a))*(X(c)-X(b))<=(Y(c)-Y(b))*(X(b)-X(a));
}
void update(int id)
{
if(head>=last)q[++last]=id;
else
{
while(head<last&&check(q[last-1],q[last],id))last--;
q[++last]=id;
}
}
int query(ld x)
{
if(head==last)return q[head];
int l=head-1,r=last;
while(l<r-1)
{
int m=(l+r)>>1;
if(cal(q[m],x)<cal(q[m+1],x))l=m;
else r=m;
}
return q[l+1];
}
}h;
void solve(int l,int r)
{
if(l==r)return ;
int m=(l+r)>>1;
solve(l,m);
h.init();
int cnt=0;
for(int i=l;i<=m;i++)d[cnt++]=info{dp[i]*c[i]/(a[i]*c[i]+b[i]),dp[i]/(a[i]*c[i]+b[i]),i};
sort(d,d+cnt);
for(int i=0;i<cnt;i++)h.update(d[i].id);
dp[m+1]=max(dp[m+1],dp[m]);
for(int i=m+1;i<=r;i++)
{
if(h.head<=h.last)
{
int x=h.query(-a[i]/b[i]);
dp[i]=max(dp[i],dp[x]*(a[i]*c[x]+b[i])/(a[x]*c[x]+b[x]));
}
}
solve(m+1,r);
}
int main()
{
int n,s;scanf("%d%d",&n,&s);
for(int i=1;i<=n;i++)
{
db x,y,z;scanf("%lf%lf%lf",&x,&y,&z);
a[i]=x,b[i]=y,c[i]=z;
}
dp[1]=s;
solve(1,n);
printf("%.3f\n",(db)dp[n]);
return 0;
}
/********************
********************/
set维护:
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize(4)
//#pragma GCC optimize("unroll-loops")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define fi first
#define se second
#define db double
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define vi vector<int>
#define mod 1000000007
#define ld long double
//#define C 0.5772156649
//#define ls l,m,rt<<1
//#define rs m+1,r,rt<<1|1
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pii pair<int,int>
#define ull unsigned long long
//#define base 1000000000000000000
#define fin freopen("a.txt","r",stdin)
#define fout freopen("a.txt","w",stdout)
#define fio ios::sync_with_stdio(false);cin.tie(0)
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}
inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}
template<typename T>inline T const& MAX(T const &a,T const &b){return a>b?a:b;}
template<typename T>inline T const& MIN(T const &a,T const &b){return a<b?a:b;}
inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c,b>>=1;}return ans;}
using namespace std;
const ull ba=233;
const db eps=1e-8;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int N=100000+10,maxn=1000000+10,inf=0x3f3f3f3f;
struct node{
ld x,y;
mutable ld k;
node(){}
node(ld _x,ld _y,ld _k){x=_x,y=_y,k=_k;}
bool operator <(const node&rhs)const{
if(rhs.y==-1e15)return k>rhs.k;
return x<rhs.x||(x==rhs.x&&y<rhs.y);
}
};
struct hull:set<node>{
bool bad(iterator it)
{
if(it==begin()||next(it)==end())return 0;
return (ld)(it->y-prev(it)->y)*(next(it)->x-it->x)<=(ld)(next(it)->y-it->y)*(it->x-prev(it)->x);
}
void cal(iterator it)
{
if(next(it)==end())it->k=-1e15;
else it->k=(ld)(next(it)->y-it->y)/(next(it)->x-it->x);
}
void update(node x)
{
if(find(x)!=end())return ;
iterator it=insert(x).fi;
if(bad(it)){erase(it);return ;}
while(it!=begin()&&bad(prev(it)))erase(prev(it));
while(next(it)!=end()&&bad(next(it)))erase(next(it));
cal(it);
if(it!=begin())cal(prev(it));
}
ld query(ld k)
{
if(size()==0)return 0;
auto it=lower_bound(node(0,-1e15,-k));
// printf("%d %f %f ---\n",size(),(db)it->x,(db)it->y);
return it->y+it->x*k;
}
}h;
ld dp[N],a[N],b[N],c[N];
int main()
{
int n,s;scanf("%d%d",&n,&s);
for(int i=1;i<=n;i++)
{
db x,y,z;scanf("%lf%lf%lf",&x,&y,&z);
a[i]=x,b[i]=y,c[i]=z;
}
dp[1]=s;
for(int i=2;i<=n;i++)
{
dp[i]=dp[i-1];
h.update(node(dp[i-1]*c[i-1]/(a[i-1]*c[i-1]+b[i-1]),dp[i-1]/(a[i-1]*c[i-1]+b[i-1]),0));
dp[i]=max(dp[i],h.query(a[i]/b[i])*b[i]);
// printf("%f\n",(db)(h.query(a[i]/b[i])*b[i]));
}
// printf("%f %f\n",(db)(*next(h.begin())).x,(db)(*next(h.begin())).y);
printf("%.3f\n",(db)dp[n]);
return 0;
}
/********************
********************/