BZOJ.1492.[NOI2007]货币兑换(DP 斜率优化 CDQ分治/Splay)

矫情吗；* 2021-10-01 01:24 264阅读 0赞

**[BZOJ][]  
[洛谷][Link 1]**

如果某天能够赚钱，那么一定会在这天把手上的金券全卖掉。同样如果某天要买，一定会把所有钱花光。

那么令\\(f\_i\\)表示到第\\(i\\)天所拥有的最多钱数（此时手上没有任何金券），可以选择什么都不干，\\(f\_i=f\_\{i-1\}\\)；也可以从之前的某一天\\(j\\)花\\(f\_j\\)的钱买金券，在第\\(i\\)天全卖掉。用第\\(j\\)天的信息算一下买了多少\\(A,B\\)，就可以得到第\\(i\\)天卖了多少钱。

所以有\\(f\_i=\\max\\\{f\_\{i-1\},\\ A\_i\\frac\{f\_jk\_j\}\{A\_jk\_j+B\_j\}+B\_i\\frac\{f\_j\}\{A\_jk\_j+B\_j\}\\\}\\)。

把后面那部分写成直线的形式：\\(\\frac\{f\_i\}\{B\_i\}-\\frac\{A\_i\}\{B\_i\}\*\\frac\{f\_jk\_j\}\{A\_jk\_j+B\_j\}=\\frac\{f\_j\}\{A\_jk\_j+B\_j\}\\)，令\\(x\_j=\\frac\{f\_jk\_j\}\{A\_jk\_j+B\_j\},\\ y\_j=\\frac\{f\_j\}\{A\_jk\_j+B\_j\}\\)，\\(\\frac\{f\_i\}\{B\_i\}-\\frac\{A\_i\}\{B\_i\}x\_j=y\_j\\)。要求用\\(k=-\\frac\{A\_i\}\{B\_i\}\\)的直线去切\\((x\_j,y\_j)\\)使得截距最大，也就是维护上凸壳。

但\\(x\\)即每个决策点不是单调的，就需要平衡树/CDQ分治去维护凸包。

**CDQ分治：**

先将所有点按斜率\\(k\\)排序。

先处理完左区间询问，然后将左区间按横坐标\\(x\\)归并排好序。这样处理右区间询问的时候（现在只考虑当前左区间对整个右区间询问的影响，也就是要对左区间维护上凸壳），左区间的\\(x\\)有序就可以直接用单调栈把上凸壳维护出来了。

而右区间已经按斜率\\(k\\)排好序了，所以可以\\(O(n)\\)在上凸壳中得到最优解（实现当前整个左区间对右区间的转移）。

当递归到\\(l=r\\)，就说明已经处理完该点\\(l\\)之前的点对\\(l\\)的影响了，就可以直接得到\\(f\_l\\)的值（顺便要和\\(f\_\{l-1\}\\)取\\(\\max\\)）并更新\\(l\\)这个决策点的信息了。

**平衡树：**

节点按\\(x\\)排序。每个节点维护与左边点和右边点的斜率\\(lk,rk\\)。（树上的节点都是凸包上的，凸包内部的就不要了）

对于新的决策点\\(x\\)，直接先插入到平衡树中。

然后将\\(x\\)转到根。先找左边第一个能与\\(x\\)构成凸包的点：若当前点\\(y\\)与前一个点的斜率\\(lk\\gt k(x,y)\\)，那么如果\\(y\\)右边还有在凸包上的点，就继续向右找（没有就结束）。否则若\\(lk\\lt k(x,y)\\)，则应继续往左找。

找右边第一个能与\\(x\\)构成凸包的点同理。

最后，如果\\(x\\)就在凸包里面，即\\(lk(x)<rk(x)\\)，就要把\\(x\\)从平衡树中删掉。

查询就根据斜率直接查询最优决策点了。

复杂度都是\\(O(n\\log n)\\)。

--------------------

**CDQ分治：**

//12648kb 792ms #include <cmath> #include <cstdio> #include <cctype> #include <algorithm> //#define gc() getchar() #define MAXIN 500000 #define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++) #define eps 1e-9 typedef long long LL; const int N=1e5+5; const double INF=1e17; double f[N],read(); char IN[MAXIN],*SS=IN,*TT=IN; struct Node { int id; double A,B,k,Rate,x,y; inline void Init(int i) { id=i,A=read(),B=read(),k=-A/B,Rate=read(); } bool operator <(const Node &x)const { return k<x.k; } }q[N]; inline double read() { double x=0,y=0.1;register char c=gc(); for(;!isdigit(c)&&c!='.';c=gc()); for(;isdigit(c);x=x*10+c-'0',c=gc()); for(c=='.'&&(c=gc());isdigit(c);x+=(c-'0')*y,y*=0.1,c=gc()); return x; } inline double GetK(int i,int j) { return fabs(q[i].x-q[j].x)<=eps?(q[i].y<q[j].y?-INF:INF):(q[i].y-q[j].y)/(q[i].x-q[j].x); // return fabs(q[i].x-q[j].x)<=eps?INF:(q[i].y-q[j].y)/(q[i].x-q[j].x); } void CDQ(int l,int r) { static int sk[N]; static Node tmp[N]; if(l==r) { f[l]=std::max(f[l],f[l-1]); q[l].y=f[l]/(q[l].A*q[l].Rate+q[l].B), q[l].x=q[l].y*q[l].Rate; return; } int mid=l+r>>1,p1=l,p2=mid+1; for(int i=l; i<=r; ++i)//将前mid个询问放在左边 后mid个放在右边 q[i].id<=mid?tmp[p1++]=q[i]:tmp[p2++]=q[i]; for(int i=l; i<=r; ++i) q[i]=tmp[i]; CDQ(l,mid); int top=0; for(int i=l; i<=mid; ++i) { while(top>=2 && GetK(i,sk[top])>GetK(sk[top],sk[top-1])) --top; sk[++top]=i; } for(int i=mid+1; i<=r; ++i) { while(top>=2 && GetK(sk[top],sk[top-1])<q[i].k) --top; int j=sk[top]; f[q[i].id]=std::max(f[q[i].id],q[i].A*q[j].x+q[i].B*q[j].y); } CDQ(mid+1,r); p1=l,p2=mid+1; int p=l;//处理完整个区间后按x排序 while(p1<=mid && p2<=r) q[p1].x<=q[p2].x?tmp[p++]=q[p1++]:tmp[p++]=q[p2++]; while(p1<=mid) tmp[p++]=q[p1++]; while(p2<=r) tmp[p++]=q[p2++]; for(int i=l; i<=r; ++i) q[i]=tmp[i]; } int main() { int n=read(); f[0]=read(); for(int i=1; i<=n; ++i) q[i].Init(i); std::sort(q+1,q+1+n), CDQ(1,n); printf("%.3lf\n",f[n]); return 0; }

--------------------

**Splay：**（快好多啊）

//6196kb 340ms #include <cmath> #include <cstdio> #include <cctype> #include <algorithm> //#define gc() getchar() #define MAXIN 300000 #define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++) #define eps 1e-9 typedef long long LL; const int N=1e5+5; const double INF=1ll<<60; double f[N],X[N],Y[N]; char IN[MAXIN],*SS=IN,*TT=IN; inline double read() { double x=0,y=0.1;register char c=gc(); for(;!isdigit(c)&&c!='.';c=gc()); for(;isdigit(c);x=x*10+c-'0',c=gc()); for(c=='.'&&(c=gc());isdigit(c);x+=(c-'0')*y,y*=0.1,c=gc()); return x; } inline double GetK(int i,int j) { return fabs(X[i]-X[j])<eps?INF:(Y[i]-Y[j])/(X[i]-X[j]); } struct SPLAY { #define ls son[x][0] #define rs son[x][1] int root,tot,fa[N],son[N][2]; double lk[N],rk[N]; void Rotate(int x,int &k) { int a=fa[x],b=fa[a],l=son[a][1]==x,r=l^1; if(a==k) k=x; else son[b][son[b][1]==a]=x; fa[a]=x, fa[x]=b, fa[son[x][r]]=a, son[a][l]=son[x][r], son[x][r]=a; } void Splay(int x,int &k) { while(x!=k) { int a=fa[x]; if(a!=k) son[a][1]==x^son[fa[a]][1]==a?Rotate(x,k):Rotate(a,k); Rotate(x,k); } } int Find(double k) { int x=root; while(x) { if(lk[x]>=k && rk[x]<=k) return x; if(lk[x]<k) x=son[x][0]; else x=son[x][1]; } return x; } int Pre(int x) { int y=son[x][0],res=y; while(y) { if(lk[y]>=GetK(x,y)) res=y, y=son[y][1]; else y=son[y][0]; } return res; } int Nxt(int x) { int y=son[x][1],res=y; while(y) { if(rk[y]<=GetK(x,y)) res=y, y=son[y][0]; else y=son[y][1]; } return res; } void Insert(int x,double xx) { int f=0,p=x; x=root; while(x) f=x, x=son[x][xx>X[x]]; x=p, fa[x]=f, son[f][xx>X[f]]=x; Splay(x,root); } void Maintain(int x) { if(ls) { int y=Pre(x); Splay(y,ls), son[y][1]=0; lk[x]=rk[y]=GetK(x,y); } else lk[x]=INF; if(rs) { int y=Nxt(x); Splay(y,rs), son[y][0]=0; rk[x]=lk[y]=GetK(x,y); } else rk[x]=-INF; if(lk[x]<=rk[x]) { int y=rs; fa[root=ls]=0, son[root][1]=y, fa[y]=root; rk[root]=lk[y]=GetK(root,y); } } }T; int main() { int n=read(); f[0]=read(); for(int i=1; i<=n; ++i) { double A=read(),B=read(),Rate=read(); int j=T.Find(-A/B); f[i]=std::max(f[i-1],A*X[j]+B*Y[j]); Y[i]=f[i]/(A*Rate+B), X[i]=Y[i]*Rate; T.Insert(i,X[i]), T.Maintain(i); } printf("%.3lf\n",f[n]); return 0; }

转载于:https://www.cnblogs.com/SovietPower/p/10111492.html

[BZOJ]: https://lydsy.com/JudgeOnline/problem.php?id=1492
[Link 1]: https://www.luogu.org/problemnew/show/P4027