经典的1D1D动态规划题目（这里就是1D1D动态规划经典的第二种， 平衡树去维护 f(n) = min{a[n]*x(i) + b[n]*y(i)}）
http://wenku.baidu.com/link?url=oWsqGQ7qjdM-ASnQBP6KmZRc8yYXyxbM3Czq_rhWvXn7IywrI8oqn3EuUs7AtecS04vznCfuHe3l-9DvBjZAwiX4ZApFpQHH1h_vBZ-7DSa
标准做法是平衡树维护凸壳，但实际上还有更简洁的分治法。
首先分析一下题目，对于任意一天，一定是贪心地买入所有货币或者卖出所有货币是最优的，因为有便宜我们就要尽量去占，有亏损就一点也不去碰。于是我们得到方程：
f[i]=max{f[j]/(a[j]*rate[j]+b[j])*rate[j]*a[i]+f[j]/(a[j]*rate[j]+b[j])*b[i]}
其中，x[j]=f[j]/(a[j]*rate[j]+b[j])*rate[j]表示第j天最多可以拥有的A货币的数量
y[j]=f[j]/(a[j]*rate[j]+b[j])表示第j天最多可以拥有的B货币的数量
说到cdq分治和整体二分的区别是， cdq分治是对操作进行离线二分， 而整体二分是对答案进行整体的二分
这下终于茅塞顿开了
http://www.cnblogs.com/zig-zag/archive/2013/04/24/3039418.html 这篇代码写的很赞 真的是如励志铭一样：“AC without art, no better than WA !”
http://blog.csdn.net/thy_asdf/article/details/46686351 这篇是功能强大的图解 ~(≧▽≦)/~
splay代码（盗用上面链接的做模板）:
cash1 #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #define maxn 120000 #define eps 1e-9 #define inf 1e9 using namespace std; int fa[maxn],c[maxn][2]; double f[maxn],x[maxn],y[maxn],lk[maxn],rk[maxn],a[maxn],b[maxn],rate[maxn]; int n,m,rot,num; inline double fabs(double x) { return (x>0)?x:-x; } inline void zigzag(int x,int &rot) { int y=fa[x],z=fa[y]; int p=(c[y][1]==x),q=p^1; if (y==rot) rot=x; else if (c[z][0]==y) c[z][0]=x; else c[z][1]=x; fa[x]=z; fa[y]=x; fa[c[x][q]]=y; c[y][p]=c[x][q]; c[x][q]=y; } inline void splay(int x,int &rot) { while (x!=rot) { int y=fa[x],z=fa[y]; if (y!=rot) if ((c[y][0]==x)xor(c[z][0]==y)) zigzag(x,rot); else zigzag(y,rot); zigzag(x,rot); } } inline void insert(int &t,int anc,int now)//加入平衡树 { if (t==0) { t=now; fa[t]=anc; return ; } if (x[now]<=x[t]+eps) insert(c[t][0],t,now); else insert(c[t][1],t,now); } inline double getk(int i,int j)//求斜率 { if (fabs(x[i]-x[j])<eps) return -inf; else return (y[j]-y[i])/(x[j]-x[i]); } inline int prev(int rot)//求可以和当前点组成凸包的右边第一个点 { int t=c[rot][0],tmp=t; while (t) { if (getk(t,rot)<=lk[t]+eps) tmp=t,t=c[t][1]; else t=c[t][0]; } return tmp; } inline int succ(int rot)//求可以和当前点组成凸包的左边第一个点 { int t=c[rot][1],tmp=t; while (t) { if (getk(rot,t)+eps>=rk[t]) tmp=t,t=c[t][0]; else t=c[t][1]; } return tmp; } inline void update(int t)//加入t点 { splay(t,rot); if (c[t][0])//向左求凸包 { int left=prev(rot); splay(left,c[rot][0]); c[left][1]=0; lk[t]=rk[left]=getk(left,t); } else lk[t]=inf; if (c[t][1])//向右求凸包 { int right=succ(rot); splay(right,c[rot][1]); c[right][0]=0; rk[t]=lk[right]=getk(t,right); } else rk[t]=-inf; if (lk[t]<=rk[t]+eps)//在原凸包内部的情况，直接删掉该点 { rot=c[t][0]; c[rot][1]=c[t][1]; fa[c[t][1]]=rot; fa[rot]=0; lk[rot]=rk[c[t][1]]=getk(rot,c[t][1]); } } inline int find(int t,double k)//找到当前斜率的位置，即找到最优值 { if (t==0) return 0; if (lk[t]+eps>=k&&k+eps>=rk[t]) return t; if (k+eps>lk[t]) return find(c[t][0],k); else return find(c[t][1],k); } int main() { //freopen("cash.in","r",stdin); //freopen("cash.out","w",stdout); scanf("%d%lf",&n,&f[0]); for (int i=1;i<=n;i++) scanf("%lf%lf%lf",&a[i],&b[i],&rate[i]); for (int i=1;i<=n;i++) { int j=find(rot,-a[i]/b[i]); f[i]=max(f[i-1],x[j]*a[i]+y[j]*b[i]); y[i]=f[i]/(a[i]*rate[i]+b[i]); x[i]=y[i]*rate[i]; insert(rot,0,i); update(i); } printf("%.3lf ",f[n]); return 0; }
cdq分治代码:
#include <iostream> #include <string.h> #include <string> #include <stdio.h> #include <algorithm> #include <math.h> #define maxn 120000 #define eps 1e-9 #define inf 1e9 using namespace std; int n; double f[maxn]; int s[maxn]; struct query { double q, a, b, rate, k; int pos; bool operator < (const query &rhs) const{ return k < rhs.k; } }q[maxn], nq[maxn]; struct point { double x, y; friend bool operator < (const point &a, const point &b) { if (a.x < b.x + eps) return true; if (fabs(a.x - b.x) <= eps && a.y - b.y < eps) return true; return false; } }p[maxn], np[maxn]; double getk(int i, int j) { if (i == 0) return -inf; if (j == 0) return inf; if (fabs(p[i].x - p[j].x) <= eps) return -inf; return (p[i].y - p[j].y) / (p[i].x - p[j].x); } void cdq(int l, int r) { if (l == r) { f[r] = max(f[r - 1], f[r]); p[r].y = f[r] / (q[r].a*q[r].rate + q[r].b); p[r].x = p[r].y*q[r].rate; return; } int mid = (l + r) >> 1, tl = l, tr = mid+1; for (int i = l; i <= r; ++i) { if (q[i].pos <= mid) nq[tl++] = q[i]; else nq[tr++] = q[i]; } for (int i = l; i <= r; ++i) q[i] = nq[i]; cdq(l, mid); int top = 0; for (int i = l; i <= mid; ++i) { while (top >= 2 && getk(i, s[top]) + eps > getk(s[top], s[top - 1])) --top; s[++top] = i; } int j = 1; for (int i = r; i >= mid + 1; --i) { while (j < top && q[i].k < getk(s[j], s[j+1]) + eps) ++j; f[q[i].pos] = max(f[q[i].pos], p[s[j]].x*q[i].a + p[s[j]].y*q[i].b); } cdq(mid + 1, r); int ll = l, lr = mid + 1; for (int i = l; i <= r; ++i) { if ((p[ll] < p[lr] || lr > r) && ll <= mid) np[i] = p[ll++]; else np[i] = p[lr++]; } for (int i = l; i <= r; ++i) p[i] = np[i]; } int main() { scanf("%d%lf", &n, &f[0]); for (int i = 1; i <= n; ++i) { scanf("%lf%lf%lf", &q[i].a, &q[i].b, &q[i].rate); q[i].pos = i; q[i].k = -q[i].a / q[i].b; } sort(q + 1, q + 1 + n); cdq(1, n); printf("%.3lf ", f[n]); return 0; }