亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

BZOJ 1492 貨幣兌換Cash

系統 1987 0

題目鏈接: 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


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

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

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 伊人久久婷婷丁香六月综合基地 | 国产玖玖在线 | 国产高清一区二区三区视频 | 99视频在线免费观看 | 超清波多野结衣精品一区 | 欧美毛片网 | 国产亚洲精品中文带字幕21页 | 国产欧美亚洲另类第一页 | 亚洲欧美日韩在线观看你懂的 | 性感美女一级毛片 | 日本免费一级 | www久久久| 久久乱码精品区中文字幕 | 国产成人精品一区二三区在线观看 | 国产精品国产三级国快看 | 天堂精品高清1区2区3区 | 日韩欧美在线一级一中文字暮 | 夜夜躁日日躁狠狠 | 91在线亚洲精品一区 | 中国国产成人精品久久 | 亚洲欧美日韩中文综合在线不卡 | 久久亚洲日本不卡一区二区 | 99久久精品国产一区二区 | 欧美一级高清视频在线播放 | 久久国产精品久久精品国产 | 一区二区三区高清 | 亚洲视频在线一区 | 美女在线看永久免费网址 | 美女视频黄a视频免费全过程在线 | 毛片一级视频 | 天天草狠狠干 | 久久精品一区二区 | h片免费 | 91在线精品老司机免费播放 | 成人午夜在线播放 | 欧美人成在线 | 日本一区二区三区四区五区 | 成人精品视频在线观看 | 欧美videossex精品4k | 国产高清国产专区国产精品 | 久久视热这只是精品222 |