题目链接： http://61.187.179.132/JudgeOnline/problem.php?id=1492
题意：有AB两种金券，n天，第一天某人有s的钱。给出每天的三个值Ai,Bi,ratei。每天可以进行的操作有两种：（1）卖掉x%(0<=x<=100):意味着分别将A种金券和B种金券分别卖掉x%，价格分别为Ai，Bi；（2）买进x元的金券：分别以Ai、Bi的价格买进两种金券买进的数量比为ratei。一天内可以进行多次操作。求n天后最大的获利。
思路：（1）首先，得到一个DP的方程,f[i]表示i天后的最大获利（最大获利必然是把所有金券全部卖了），则f[i]=max(f[i-1],Ai*Yi+Bi*Xi)，Xi和Yi表示第i天可以有的金券数量，对于Xi和Yi的计算，我们可以枚举1<=j<=i-1，将f[j]的钱全部全部买成金券，保存到第i天。想想，有没有可能这样：把第j天的钱用一部分买金券，剩下一些钱，然后将买的金券在第i天卖掉再加上第j天剩下的钱最优。这是不可能的，要么在第j天把所有钱全部买成金券，要么一点不买，不可能有折中的情况是最优的。这个DP的复杂付O(n^2)，下面进行优化。
（2）上面的DP方程其实就是求P=Ai*Yi+Bi*Xi的最大值，我们将(Xi,Yi)看做坐标上的点，那么得到：Y=-Bi/Ai*X+P/Ai，要使得P最大，也就是在y轴的截距最大。显然，这个直线的斜率小于0。这个(Xi,Yi)来自之前的i-1个已经计算出的f值，我们就是要在这i-1个中找到一个(Xi,Yi)使得P最大。我们可以看做将Y=-Bi/Ai*X+P/Ai这条直线从y轴正无穷向下平移，首先碰到的点就是使得P最大的点，那么我们就是要将之前的点维护成一个上凸壳，使得相邻的斜率单调递减，且支持插入更新、查找，用splay维护，按照x坐标。每次查找时，找到跟当前斜率-Bi/Ai最接近的点即是最优的；插入时，按照插入的x坐标找到其应该插入的位置。然后判断要不要插入，找到其前驱pre和后继next，若与其前驱的斜率小于与其后继的斜率，那么无需插入；否则插入，然后更新。比如对于前驱pre和前驱的前驱pre1，若pre1和当前点的斜率大于pre1和pre的斜率，那么pre需要删除。
double a[N],b[N],rate[N];
int n;
int c[N][2],p[N],root;
double X[N],Y[N],slope[N];
void zig(int x)
{
int y=p[x],z=p[y];
c[y][0]=c[x][1];
p[c[x][1]]=y;
c[x][1]=y;
if(z)
{
if(c[z][0]==y) c[z][0]=x;
else c[z][1]=x;
}
p[x]=p[y];
p[y]=x;
}
void zag(int x)
{
int y=p[x],z=p[y];
c[y][1]=c[x][0];
p[c[x][0]]=y;
c[x][0]=y;
if(z)
{
if(c[z][0]==y) c[z][0]=x;
else c[z][1]=x;
}
p[x]=p[y];
p[y]=x;
}
void splay(int x,int goal)
{
if(!x) return;
int y,z;
while(p[x]!=goal)
{
y=p[x]; z=p[y];
if(z!=goal)
{
if(c[z][0]==y)
{
if(c[y][0]==x) zig(y),zig(x);
else zag(x),zig(x);
}
else
{
if(c[y][1]==x) zag(y),zag(x);
else zig(x),zag(x);
}
}
else
{
if(c[y][0]==x) zig(x);
else zag(x);
}
}
if(!goal) root=x;
}
int pre(int u)
{
splay(u,0);
u=c[u][0];
while(c[u][1]) u=c[u][1];
return u;
}
int next(int u)
{
splay(u,0);
u=c[u][1];
while(c[u][0]) u=c[u][0];
return u;
}
double get(int now)
{
int i=root;
double s=atan(-b[now]/a[now]);
while(1)
{
if(s<slope[i])
{
if(!c[i][1]) break;
i=c[i][1];
}
else
{
if(!c[i][0]) break;
i=c[i][0];
}
}
while(slope[i]<s) i=pre(i);
splay(i,0);
return X[i]*b[now]+Y[i]*a[now];
}
inline void del(int x)
{
int i=pre(x),j=next(x);
splay(i,0);
splay(j,i);
c[j][0]=0;
}
void insert(double x,double y)
{
int i=root,j,temp;
while(1)
{
if(x>X[i])
{
if(!c[i][1]) break;
i=c[i][1];
}
else
{
if(!c[i][0]) break;
i=c[i][0];
}
}
X[++n]=x; Y[n]=y; p[n]=i;
if(x>X[i]) c[i][1]=n;
else c[i][0]=n;
i=pre(n),j=next(n);
if(i&&j&&atan2(y-Y[i],x-X[i])<atan2(Y[j]-y,X[j]-x))
{
del(n);
return;
}
temp=pre(i);
while(temp&&atan2(y-Y[i],x-X[i])>=slope[i])
{
del(i);
i=temp;
temp=pre(i);
}
if(i) slope[n]=atan2(y-Y[i],x-X[i]);
temp=next(j);
while(temp&&atan2(Y[j]-y,X[j]-x)<=slope[temp])
{
del(j);
j=temp;
temp=next(j);
}
if(j) slope[j]=atan2(Y[j]-y,X[j]-x);
}
int m;
double s;
int main()
{
RD(m); RD(s);
int i;
double ans=s,x,y,temp;
FOR1(i,m) RD(a[i],b[i]),RD(rate[i]);
X[1]=ans/(rate[1]*a[1]+b[1]);
Y[1]=rate[1]*X[1];
slope[1]=0;
n=1; root=1;
for(i=2;i<=m;i++)
{
temp=get(i);
if(temp>ans) ans=temp;
x=ans/(rate[i]*a[i]+b[i]);
y=x*rate[i];
insert(x,y);
}
printf("%.3lf\n",ans);
return 0;
}
