洛谷P4027 貨幣兌換

2022-09-23 02:02:04 字數 2368 閱讀 5902

小 y 最近在一家金券交易所工作。該金券交易所只發行交易兩種金券:a 紀念券(以下簡稱 a 券)和 b 紀念券(以下簡稱 b 券)。每個持有金券的顧客都有一個自己的帳戶。金券的數目可以是一個實數。

每天隨著市場的起伏波動,兩種金券都有自己當時的價值,即每一單位金券當天可以兌換的人民幣數目。我們記錄第 k 天中 a 券和 b 券的價值分別為 \(a_k\) 和\(b_k\) (元/單位金券)。

為了方便顧客,金券交易所提供了一種非常方便的交易方式:比例交易法。

比例交易法分為兩個方面:

a) 賣出金券:顧客提供一個[0,100]內的實數 op 作為賣出比例,其意義為:將 op%的 a 券和 op%的 b 券以當時的價值兌換為人民幣;

b) **金券:顧客支付 ip 元人民幣,交易所將會兌換給使用者總價值為ip 的金券,並且,滿足提供給顧客的 a 券和 b 券的比例在第 k 天恰好為 \(rate_k\);

例如,假定接下來 3 天內的 \(a_k\) 、\(b_k\) 、\(rate_k\) 的變化分別為:

時間\(a_k\)

\(b_k\)

\(rate_k\)

第一天111

第二天122

第三天223

假定在第一天時,使用者手中有 100 元人民幣但是沒有任何金券。

使用者可以執行以下的操作:

時間使用者操作

人民幣(元)

a券的數量

b券的數量開戶無

\(100\)00

第一天** \(100\)元050

50第二天

賣出 \(50\%\)

7525

25第二天

** \(60\)元

1555

40第三天

賣出 \(100\%\)

2050

0注意到,同一天內可以進行多次操作。

小 y 是一個很有經濟頭腦的員工,通過較長時間的運作和**測算,他已經知道了未來 n 天內的 a 券和 b 券的價值以及 rate。他還希望能夠計算出來,如果開始時擁有 s 元錢,那麼 n 天后最多能夠獲得多少元錢。

很容易證明每次操作必然全部**或賣出。這個結論十分好證,因為**或賣出的比例是固定的。

所以一定是不斷全部**,全部賣出的過程重複。設 \(f[i]\) 表示在第 \(i\) 天全部賣出的最大收益,那麼考慮列舉 \(j\in[1,i)\),表示最近一次**是在第 \(j\) 天。已知總**的總花費為 \(f[j]\),設**了 \(x\) 單位 b 券,那麼可以列出方程

\[x·b[j]+x·r[j]·a[j]=f[j]

\]解得 \(x=\frac\)。令 \(t[j]=x=\frac\),那麼** a 券 \(t[j]·r[i]\) 單位,** b 券 \(t[j]\) 單位。

所以有\[f[i]=max(f[i-1],t[j]·b[i]+t[j]·r[j]·a[i])

\]先不考慮 \(f[i-1]\),得到 \(f[i]=t[j]·b[i]+t[j]·r[j]·a[i]\)。我們發現這個多項式中包含 \(i,j\) 兩項的並不是一個單項式而是多項式,所以不可以直接優化。

但是我們將等號兩邊同時除以 \(a[i]\) 可以得到 \(\frac=\frac·t[j]+t[j]·r[j]\)。移項得 \(t[j]·r[j]=-\frac·t[j]+\frac\),而這個式子就是一個標準的 "\(y=kx+b\)"。

考慮使用斜率優化。但是一般的斜率優化因為要按點橫座標順序加點維護凸殼,但是此題每一個點的座標為 \((t[j],t[j]·r[j])\),其中橫座標 \(t[j]\) 是不滿足單調性的。一種直觀的維護方式是平衡樹維護凸殼。但是有一種相對簡單的方式為 cdq 分治維護凸殼。

按照時間進行分治,對於一個區間 \([l,r]\),先將其左子區間維護好,然後計算左子區間對右子區間的貢獻。將左子區間按照點的橫座標升序排序,右子區間按照斜率 \(-\frac\) 升序排序。然後指標掃描計算貢獻即可。

計算完後再將右子區間進行分治。注意當 \(l=r\) 時,\(f[l]\) 要與 \(f[l-1]\) 取 \(\max\)。

時間複雜度 \(o(n\log^2 n)\),似乎採用歸併排序可以降至 \(o(n\log n)\)。

#include using namespace std;

typedef long long ll;

const int n=100010;

const double eps=1e-7;

int n,top,st[n];

double f[n];

struct node

a[n];

bool cmp1(node x,node y)

cdq(1,n);

printf("%.8lf",f[n]);

return 0;

}

luogu P4027 NOI2007 貨幣兌換

luogu ws 這裡設 f i 為前 i 天內得到的最多錢數,轉移就考慮在第 i 天把錢變成券 然後列舉 i 的 j 在第 j 天換成錢...

洛谷p1009

用高精度計算出s 1 2 3 n n 50 其中 表示階乘,例如 5 5 4 3 2 1。 一個正整數n。 一個正整數s,表示計算結果。 輸...

洛谷p1101

給一n times nn n的字母方陣,內可能蘊含多個 yizhong 單詞。單詞在方陣中是沿著同一方向連續擺放的。擺放可沿著 88 個方向...