【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 100
1 1 1
1 2 2
2 2 3

Sample Output

225.000

HINT

題解：好吧該啃的硬骨頭還是要啃的~

如果感覺像斜率優化，那么我們來試著列方程吧！顯然，我們的所有操作肯定是：傾巢買入-傾巢賣出-傾巢買入...那么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分治的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。