正題

題目鏈接:https://www.luogu.com.cn/problem/P4027

---

題目大意

$n$天開始時有$S$元錢，每天$A$種股票價格為$a_i$,$B$種價格為$b_i$。然后出售必須$A$和$B$出售相同比例，買入時$A$和$B$必須按照$r_i$的比例買入。

求最后的錢最多是多少

---

解題思路

首先考慮$dp$。

假設(shè)有情況是只出售一部分最賺，然后之后（中間不買入）再出售一部分能更賺錢，那么將前面的放在最后出售的那一天出售完顯然不會更虧，所以顯然不成立，所以每次出售必定是全部出售完。同理，每次買入也是全部買入。

那么我們可以設(shè)$f_i$表示第$i$天的最多錢數(shù)，那么全部買入時$A$股的數(shù)量為$x_i=\frac{f_i{r}_i}{a_i{r}_i+b_i}$，$B$股數(shù)量為$y_i=\frac{f_i}{a_i{r}_i+b_i}$。有方程式$$f_i=max\{f_{i?1},x_j{a}_i+y_j{b}_i\}$$

然后考慮優(yōu)化方程$$f_i=x_j{a}_i+y_j{b}_i$$

$$?y_j=?\frac{a_i}{b_i}{x}_j+\frac{f_i}{b_i}$$
有一條斜率為$?\frac{a_i}{b_i}$經(jīng)過決策點(diǎn)$(x_j,y_j)$

因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$b_i$固定，所以是要求截距$\frac{f_i}{b_i}$最大，那么顯然每個可能的決策點(diǎn)$(x_j,y_j)$構(gòu)成一個上凸殼。（斜率遞減）

若已經(jīng)構(gòu)建了上凸殼，那么如何求答案，首先我們要找到第一個位置使得該決策點(diǎn)的前面的邊的斜率大于$?\frac{a_i}{b_i}$，后面那條邊的斜率小于$?\frac{a_i}{b_i}$即可。

由于都不是單調(diào)的，所以我們可以用$CDQ$分治。

每次計(jì)算完$[l,mid]$后我們可以用前面的$[l,mid]$用單調(diào)棧儲存凸殼，然后讓$[mid+1,r]$保持$?\frac{a_i}{b_i}$遞增，然后即可雙指針尋找答案。

時間復(fù)雜度$O(n{\log }^{2}n)$(如果用歸并排序好像可以做到$O(n\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=1e5+10; int n,p[N],q[N],s[N],tot; double f[N],x[N],y[N],ra[N],a[N],b[N]; double slope(int a,int b) {if(fabs(x[a]-x[b])<1e-9)return 1e9;return (y[a]-y[b])/(x[a]-x[b]); } bool cmp(int i,int j) {return a[i]/b[i]>a[j]/b[j];} bool cMp(int i,int j) {return x[i]<x[j];} void cdq(int l,int r){if(l==r){f[l]=max(f[l-1],f[l]);x[l]=f[l]*ra[l]/(a[l]*ra[l]+b[l]);y[l]=f[l]/(a[l]*ra[l]+b[l]);return;}int mid=(l+r)>>1,t1=l,t2=mid+1;for(int i=l;i<=r;i++)if(p[i]<=mid)q[t1++]=p[i];else q[t2++]=p[i];for(int i=l;i<=r;i++)p[i]=q[i];cdq(l,mid);tot=0;for(int i=l;i<=mid;i++){while(tot>1&&slope(s[tot],p[i])>slope(s[tot-1],s[tot]))tot--;s[++tot]=p[i];}for(int i=mid+1;i<=r;i++){while(tot>1&&slope(s[tot-1],s[tot])<-a[p[i]]/b[p[i]])tot--;int pos=s[tot];f[p[i]]=max(f[p[i]],x[pos]*a[p[i]]+y[pos]*b[p[i]]);}cdq(mid+1,r);sort(p+l,p+1+r,cMp); } int main() {scanf("%d%lf",&n,&f[0]);for(int i=1;i<=n;i++)scanf("%lf%lf%lf",&a[i],&b[i],&ra[i]),p[i]=i;sort(p+1,p+1+n,cmp);cdq(1,n);printf("%.3lf",f[n]); }

總結(jié)

以上是生活随笔為你收集整理的P4027-[NOI2007]货币兑换【斜率优化dp,CDQ分治】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。