Description

Input

第一行兩個正整數N、S，分別表示小Y 能預知的天數以及初始時擁有的錢數。 接下來N 行，第K 行三個實數AK、BK、RateK，意義如題目中所述

Output

只有一個實數MaxProfit，表示第N 天的操作結束時能夠獲得的最大的金錢 數目。答案保留3 位小數。

Sample Input

3 100
1 1 1
1 2 2
2 2 3

Sample Output

225.000

HINT

測試數據設計使得精度誤差不會超過10-7。
對于40%的測試數據，滿足N ≤ 10；
對于60%的測試數據，滿足N ≤ 1 000；
對于100%的測試數據，滿足N ≤ 100 000；

1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 using namespace std; 6 const double eps=1e-8; 7 const int maxn=100010; 8 struct Node{ 9 double a,b,r,x,y,k; 10 int id; 11 }d[maxn],t[maxn]; 12 double f[maxn]; 13 int st[maxn],cnt,n; 14 double Abs(double a){return a>0?a:-a;} 15 double K(int a,int b){ 16 if(Abs(d[a].x-d[b].x)<eps)return 1e20; 17 return (d[a].y-d[b].y)/(d[a].x-d[b].x); 18 } 19 void Solve(int l,int r){ 20 if(l==r){ 21 f[l]=max(f[l],f[l-1]); 22 d[l].y=f[l]/(d[l].r*d[l].a+d[l].b); 23 d[l].x=d[l].y*d[l].r; 24 return; 25 } 26 int mid=(l+r)>>1,t1=l,t2=mid+1; 27 for(int i=l;i<=r;i++){ 28 if(d[i].id<=mid) 29 t[t1++]=d[i]; 30 else 31 t[t2++]=d[i]; 32 } 33 for(int i=l;i<=r;i++)d[i]=t[i]; 34 Solve(l,mid); 35 cnt=0; 36 for(int i=l;i<=mid;i++){ 37 while(cnt>1&&K(i,st[cnt])-K(st[cnt],st[cnt-1])>=eps)cnt--; 38 st[++cnt]=i; 39 } 40 int fir=1; 41 for(int i=mid+1;i<=r;i++){ 42 while(fir<cnt&&K(st[fir+1],st[fir])-d[i].k>=eps)fir++; 43 f[d[i].id]=max(f[d[i].id],d[st[fir]].x*d[i].a+d[st[fir]].y*d[i].b); 44 } 45 Solve(mid+1,r); 46 t1=l;t2=mid+1; 47 for(int i=l;i<=r;i++){ 48 if(t2==r+1||(d[t2].x-d[t1].x>=eps||Abs(d[t2].x-d[t1].x)<eps&&d[t2].y-d[t1].y>=eps)&&t1<=mid) 49 t[i]=d[t1++]; 50 else 51 t[i]=d[t2++]; 52 } 53 for(int i=l;i<=r;i++) 54 d[i]=t[i]; 55 } 56 57 58 bool cmp(Node a,Node b){ 59 return a.k>b.k; 60 } 61 int main(){ 62 scanf("%d%lf",&n,&f[1]); 63 for(int i=1;i<=n;i++){ 64 scanf("%lf%lf%lf",&d[i].a,&d[i].b,&d[i].r); 65 d[i].k=-d[i].a/d[i].b; 66 d[i].id=i; 67 } 68 sort(d+1,d+n+1,cmp); 69 Solve(1,n); 70 printf("%.3lf\n",f[n]); 71 return 0; 72 }

　　這里還有Splay。

1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 const double eps=1e-8; 6 const double INF=1e20; 7 const int maxn=100010; 8 int ch[maxn][2],fa[maxn],rt,tot,n; 9 double X[maxn],Y[maxn],lk[maxn],rk[maxn],ans; 10 double fabs(double x){return (x>0)?x:-x;} 11 void Rotate(int x){ 12 int y=fa[x],g=fa[y],c=ch[y][1]==x; 13 ch[y][c]=ch[x][c^1];fa[ch[y][c]]=y; 14 ch[x][c^1]=y;fa[y]=x;fa[x]=g; 15 if(g)ch[g][ch[g][1]==y]=x; 16 } 17 18 void Splay(int x,int g=0){ 19 for(int y;(y=fa[x])!=g;Rotate(x)) 20 if(fa[y]!=g)Rotate((ch[fa[y]][1]==y)==(ch[y][1]==x)?y:x); 21 if(!g)rt=x; 22 } 23 24 double Get_K(int j,int k){ 25 if(fabs(X[j]-X[k])<=eps)return INF; 26 else return (Y[j]-Y[k])/(X[j]-X[k]); 27 } 28 29 int Get_Prev(){ 30 int p=ch[rt][0],ret=p; 31 while(p){ 32 if(Get_K(rt,p)+eps>=lk[p])p=ch[p][0]; 33 else ret=p,p=ch[p][1]; 34 } 35 return ret; 36 } 37 38 int Get_Succ(){ 39 int p=ch[rt][1],ret=p; 40 while(p){ 41 if(Get_K(p,rt)<=rk[p]+eps)p=ch[p][1]; 42 else ret=p,p=ch[p][0]; 43 } 44 return ret; 45 } 46 47 void Insert(int &r,int pre,int p){ 48 if(r==0){r=p;fa[p]=pre;return;} 49 if(X[p]<=X[r]+eps)Insert(ch[r][0],r,p); 50 else Insert(ch[r][1],r,p); 51 } 52 53 void Update(int p){ 54 Splay(p); 55 if (ch[p][0]){ 56 int l=Get_Prev(); 57 Splay(l,p);ch[l][1]=0; 58 lk[p]=rk[l]=Get_K(p,l); 59 } 60 else lk[p]=INF; 61 if (ch[p][1]){ 62 int r=Get_Succ(); 63 Splay(r,p); ch[r][0]=0; 64 rk[p]=lk[r]=Get_K(r,p); 65 } 66 else rk[p]=-INF; 67 if (lk[p]<=rk[p]+eps){ 68 rt=ch[p][0]; ch[rt][1]=ch[p][1]; fa[ch[p][1]]=rt; fa[rt]=0; 69 rk[rt]=lk[ch[p][1]]=Get_K(ch[rt][1],rt); 70 } 71 } 72 73 int Get_Pos(double k){ 74 int p=rt; 75 while(p){ 76 if(lk[p]+eps>=k&&k+eps>=rk[p])break; 77 if(lk[p]<k+eps)p=ch[p][0]; 78 else p=ch[p][1]; 79 } 80 return p; 81 } 82 83 double Get_Ans(double a,double b){ 84 int p=Get_Pos(-b/a); 85 return a*Y[p]+b*X[p]; 86 } 87 88 int main(){ 89 #ifndef ONLINE_JUDGE 90 freopen("cash.in","r",stdin); 91 freopen("cash.out","w",stdout); 92 #endif 93 double a,b,rate; 94 scanf("%d%lf",&n,&ans); 95 for(int i=1;i<=n;i++){ 96 scanf("%lf%lf%lf",&a,&b,&rate); 97 if(i!=1)ans=max(ans,Get_Ans(a,b)); 98 X[i]=ans/(rate*a+b); 99 Y[i]=X[i]*rate; 100 Insert(rt,0,i); 101 Update(i); 102 } 103 printf("%.3f\n",ans); 104 return 0; 105 }

?

轉載于:https://www.cnblogs.com/TenderRun/p/5307998.html

總結

以上是生活随笔為你收集整理的斜率优化(CDQ分治，Splay平衡树)：BZOJ 1492: [NOI2007]货币兑换Cash的全部內容，希望文章能夠幫你解決所遇到的問題。

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