題意：有 A，B 兩種金券，給出 $n$ 天內分別的單位價格和可以購買的數量的比例。開始有 $S$ 元，求 $n$ 天后最多能有多少元。

提示：每次操作一定全買全賣

$n\le 10^5$

設 $f_n$ 表示第 $n$ 天結束后手上最多有多少錢，允許之前某一天賣完后不動留到第 $n$ 天。

轉移時如果第 $n$ 天沒賣，就留下 $f_{n?1}$；否則枚舉賣出去的金券是哪天買的。

即

$$f_i=\max \{f_{i?1},\underset{1\le j<i}{\max }(a_i{x}_j+b_i{y}_j)\}$$

其中 $x_j,y_j$ 表示在第 $j$ 天兩種金券最大能買到的數量，顯然能同時取最大值。

即

$$x_i=\frac{r_i{f}_i}{r_i{a}_i+b_i},y_i=\frac{f_i}{r_i{a}_i+b_i}$$

考慮一個決策算出的值為 $t$

$$t=a_i{x}_j+b_i{y}_j$$

$$y_j=?\frac{a_i}{b_i}{x}_j+\frac{t}{b_i}$$

也就是過 $(x_j,y_j)$ 斜率為 $?\frac{a_i}{b_i}$ 的直線中截距最大的

考慮斜率優化，維護一個上凸殼即可

但 $x$ 坐標不單調，需要用平衡樹/李超線段樹/CDQ分治

本文采用 CDQ 分治

核心思想是按 $x$ 遞增順序維護左半邊的點，用單調棧現求凸殼，右邊維護單調遞增的詢問斜率并查詢。

具體而言，因為斜率是輸入時就確定的，先在外面把斜率從小到大排序，分治時當前區間是對應的真實標號的區間按斜率排序后的結果。然后

用類似快排的東西分出左右部分

分治左半邊

求左半邊對右邊的貢獻，即左半邊求凸殼，右邊再在凸殼上掃一遍。

分治右半邊

按 $x$ 坐標歸并兩邊的點

復雜度 $O(n\log n)$

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <algorithm> #include <cmath> #define MAXN 100005 using namespace std; const double eps=1e-9,inf=1e9; double f[MAXN]; struct node{double x,y,k,a,b,r;int id;}p[MAXN],t1[MAXN],t2[MAXN]; inline bool cmp(const node& x,const node& y){return x.k<y.k;} inline double slope(const node& a,const node& b) {if (fabs(a.x-b.x)<eps) return inf;return (a.y-b.y)/(a.x-b.x); } void solve(int l,int r) {if (l==r){f[l]=max(f[l],f[l-1]);p[l].y=f[l]/(p[l].r*p[l].a+p[l].b);p[l].x=p[l].y*p[l].r;return;}int mid=(l+r)>>1;int cnt1=0,cnt2=0;for (int i=l;i<=r;i++)if (p[i].id<=mid) t1[++cnt1]=p[i];else t2[++cnt2]=p[i];for (int i=1;i<=cnt1;i++) p[l+i-1]=t1[i];for (int i=1;i<=cnt2;i++) p[mid+i]=t2[i];solve(l,mid);int tp=0;for (int i=l;i<=mid;i++) {while (tp>1&&slope(t1[tp-1],t1[tp])+eps<slope(t1[tp],p[i])) --tp;t1[++tp]=p[i]; } for (int i=mid+1;i<=r;i++){while (tp>1&&slope(t1[tp-1],t1[tp])<=p[i].k+eps) --tp;f[p[i].id]=max(f[p[i].id],p[i].a*t1[tp].x+p[i].b*t1[tp].y);}solve(mid+1,r);cnt1=l,cnt2=mid+1,tp=l;while (cnt1<=mid||cnt2<=r)if (cnt1<=mid&&(cnt2>r||p[cnt1].x<p[cnt2].x+eps)) t1[tp++]=p[cnt1++];else t1[tp++]=p[cnt2++];for (int i=l;i<=r;i++) p[i]=t1[i]; } int main() {int n;scanf("%d%lf",&n,&f[0]);for (int i=1;i<=n;i++) scanf("%lf%lf%lf",&p[i].a,&p[i].b,&p[i].r),p[i].k=-p[i].a/p[i].b,p[i].id=i;sort(p+1,p+n+1,cmp);solve(1,n);printf("%.3f",f[n]);return 0; }

總結

以上是生活随笔為你收集整理的【NOI2007】货币兑换【任意坐标斜率优化】【CDQ分治】的全部內容，希望文章能夠幫你解決所遇到的問題。

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