【BZOJ1492】[NOI2007]货币兑换Cash 斜率优化+cdq分治
【BZOJ10492】[NOI2007]貨幣兌換Cash
Description
小Y最近在一家金券交易所工作。該金券交易所只發行交易兩種金券:A紀念券(以下簡稱A券)和 B紀念券(以下簡稱B券)。每個持有金券的顧客都有一個自己的帳戶。金券的數目可以是一個實數。每天隨著市場的起伏波動,兩種金券都有自己當時的價值,即每一單位金券當天可以兌換的人民幣數目。我們記錄第 K 天中 A券 和 B券 的價值分別為 AK 和 BK(元/單位金券)。為了方便顧客,金券交易所提供了一種非常方便的交易方式:比例交易法。比例交易法分為兩個方面:(a)賣出金券:顧客提供一個 [0,100] 內的實數 OP 作為賣出比例,其意義為:將?OP% 的 A券和 OP% 的 B券 以當時的價值兌換為人民幣;(b)買入金券:顧客支付 IP 元人民幣,交易所將會兌換給用戶總價值為 IP 的金券,并且,滿足提供給顧客的A券和B券的比例在第 K 天恰好為 RateK;例如,假定接下來 3 天內的 Ak、Bk、RateK 的變化分別為: 假定在第一天時,用戶手中有 100元 人民幣但是沒有任何金券。用戶可以執行以下的操作: 注意到,同一天內可以進行多次操作。小Y是一個很有經濟頭腦的員工,通過較長時間的運作和行情測算,他已經知道了未來N天內的A券和B券的價值以及Rate。他還希望能夠計算出來,如果開始時擁有S元錢,那么N天后最多能夠獲得多少元錢。Input
輸入第一行兩個正整數N、S,分別表示小Y能預知的天數以及初始時擁有的錢數。接下來N行,第K行三個實數AK、BK、RateK,意義如題目中所述。對于100%的測試數據,滿足:0<AK≤10;0<BK≤10;0<RateK≤100;MaxProfit≤10^9。 【提示】 1.輸入文件可能很大,請采用快速的讀入方式。 2.必然存在一種最優的買賣方案滿足: 每次買進操作使用完所有的人民幣; 每次賣出操作賣出所有的金券。Output
只有一個實數MaxProfit,表示第N天的操作結束時能夠獲得的最大的金錢數目。答案保留3位小數。
Sample Input
3 1001 1 1
1 2 2
2 2 3
Sample Output
225.000HINT
題解:好吧該啃的硬骨頭還是要啃的~
如果感覺像斜率優化,那么我們來試著列方程吧!顯然,我們的所有操作肯定是:傾巢買入-傾巢賣出-傾巢買入...那么DP方程如下:
設f[i]表示在第i天,將手中所有金券都賣完,所能擁有的最多錢數,那么
$f[i]=f[i-1]\\f[i]=\min(f[j]/(a[j]\times rate[j]+b[j])*(a[i]*rate[j]+b[i]))$
將括號拆開
$f[i]=a[i]*f[j]/(a[j]\times rate[j]+b[j])*rate[j]+b[i]*f[j]/(a[j]\times rate[j]+b[j])$
感覺不太好看,設$g[i]=f[j]/(a[j]\times rate[j]+b[j])$試試?如果還是感覺不好看,因為a[i],b[i]都是常數,兩邊都除個a[i]試試?是不是好看多了?
$g[j]*rate[j]=-{b[i]\over a[i]}*g[j]+{f[i]\over a[i]}$
看起來推式子好像挺簡單的,但是x和k都不單調啊,于是我們就想找出一種辦法使得我們永遠都只需要用一些單調的x來更新一些單調的k,這就涉及到排序,怎么辦?cdq分治唄!
注意:我們整個分治過程會想辦法讓某段區間分別滿足:按x升序,按編號(時間)升序,按k降序,下面請留意。
具體做法:先將正個序列按k降序排序,然后開始分治。在分治區間[l,r]時,我們先按時間進行歸并,將時間在[l,mid]的放在左邊,然后遞歸處理左區間,在處理左區間的結束時候順便按x升序排個序(一會再說)。現在我們來處理區間[l,r],發現此時的[l,mid]滿足x升序,[mid+1,r]滿足k降序,豈不是正好可以用斜率優化?然后,我們遞歸處理右區間(也順便按x升序排個序),最后,左右區間都已經按x升序排完序了,歸并起來就好了。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cmath> using namespace std; const int maxn=100010; struct node {double A,B,f,g,k,rate,org;double x(){return g;}double y(){return g*rate;} }p[maxn],pp[maxn]; int n; int q[maxn],h,t; double ans; int rd() {int ret=0,f=1; char gc=getchar();while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();return ret*f; } bool cmpg(node a,node b) {return a.g<b.g; } bool cmpk(node a,node b) {return a.k>b.k; } double getk(int a,int b) {if(fabs(p[a].x()-p[b].x())<1e-12) return -2147483647.0;else return (p[a].y()-p[b].y())/(p[a].x()-p[b].x()); } void solve(int l,int r) {if(l==r){p[l].f=max(p[l].f,p[l-1].f);p[l].g=p[l].f/(p[l].A*p[l].rate+p[l].B);return ;}int mid=l+r>>1,i,j,h1=l,h2=mid+1;double mf=0;for(i=l;i<=r;i++){if(p[i].org<=mid) pp[h1++]=p[i];else pp[h2++]=p[i];}for(i=l;i<=r;i++) p[i]=pp[i];solve(l,mid);h=1,t=0;for(i=l;i<=mid;i++){while(h<t&&getk(q[t],q[t-1])<getk(i,q[t])) t--;q[++t]=i;mf=max(mf,p[i].f);}for(i=mid+1;i<=r;i++){while(h<t&&getk(q[h+1],q[h])>p[i].k) h++;p[i].f=max(p[i].f,p[q[h]].f/(p[q[h]].A*p[q[h]].rate+p[q[h]].B)*(p[i].A*p[q[h]].rate+p[i].B));p[i].f=max(p[i].f,mf);p[i].g=p[i].f/(p[i].A*p[i].rate+p[i].B);}solve(mid+1,r);for(h1=l,h2=mid+1,i=l;i<=r;i++){if(h1<=mid&&(h2>r||p[h1].x()<p[h2].x())) pp[i]=p[h1++];else pp[i]=p[h2++];}for(i=l;i<=r;i++) p[i]=pp[i]; } int main() {scanf("%d%lf",&n,&p[1].f);int i;for(i=1;i<=n;i++){scanf("%lf%lf%lf",&p[i].A,&p[i].B,&p[i].rate);p[i].k=-p[i].B/p[i].A,p[i].org=i;}sort(p+1,p+n+1,cmpk);solve(1,n);for(i=1;i<=n;i++) ans=max(ans,p[i].f);printf("%.3lf",ans);return 0; }?
轉載于:https://www.cnblogs.com/CQzhangyu/p/7071546.html
總結
以上是生活随笔為你收集整理的【BZOJ1492】[NOI2007]货币兑换Cash 斜率优化+cdq分治的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 学容器必须懂 bridge 网络 - 每
- 下一篇: spark-streaming问题集锦