題目鏈接： 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;
}

?

?

BZOJ 1492 貨幣兌換Cash