題目鏈接: 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;
}
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
