[BZOJ 1492][NOI2007]货币兑换Cash：CDQ分治|DP斜率优化

本文主要是介绍[BZOJ 1492][NOI2007]货币兑换Cash：CDQ分治|DP斜率优化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击这里查看原题

首先贪心的想，每次买卖必然要买空或者卖空，因为有便宜就尽量去占，于是可以得到方程：

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货币的数量
于是可以得到斜截式：y[j]=f[i]/b[i]-x[j]*a[i]/b[i]，也就是说需要得到最优的点(x[j],y[j])使截距最大，于是维护一个上凸壳。
但是斜率-a[i]/b[i]是无序的，不能直接斜率优化。一个办法是用平衡树维护凸壳，这样代码量太大，也不易于调试。
因此，接下来使用我们的重头戏——CDQ分治。
CDQ分治中我们不需要考虑右区间内各个点之间的影响，只需考虑左区间对右区间的影响，因此将左边按坐标排序，右边按斜率排序，即可套用斜率优化。

/*
User:Small
Language:C++
Problem No.:1492
*/
#include<bits/stdc++.h>
#define ll long long
#define inf 999999999
using namespace std;
const int M=1e5+5;
const double eps=1e-6;
int n,stk[M],tp;
double f[M];
struct no{double a,b,rate,k;int pos;bool operator<(no y)const{return k<y.k;}
}q[M],nq[M];
struct node{double x,y;bool operator<(node a)const{return fabs(x-a.x)<eps?y<a.y+eps:x<a.x+eps;}
}p[M],np[M];
double getk(int i,int j){return fabs(p[i].x-p[j].x)<eps?-inf:(p[i].y-p[j].y)/(p[i].x-p[j].x);
}
void solve(int l,int r){if(l==r){f[l]=max(f[l-1],f[l]);p[l].y=f[l]/(q[l].a*q[l].rate+q[l].b);p[l].x=p[l].y*q[l].rate;return;}int mid=l+r>>1,l1=l,l2=mid+1;for(int i=l;i<=r;i++){if(q[i].pos<=mid) nq[l1++]=q[i];else nq[l2++]=q[i];}for(int i=l;i<=r;i++) q[i]=nq[i];solve(l,mid);tp=0;for(int i=l;i<=mid;i++){while(tp>1&&getk(i,stk[tp])+eps>getk(stk[tp],stk[tp-1])) tp--;stk[++tp]=i;}for(int i=r,j=1;i>=mid+1;i--){while(j<tp&&q[i].k<getk(stk[j],stk[j+1])+eps) j++;f[q[i].pos]=max(f[q[i].pos],p[stk[j]].x*q[i].a+p[stk[j]].y*q[i].b);}solve(mid+1,r);l1=l,l2=mid+1;for(int i=l;i<=r;i++){np[i]=((p[l1]<p[l2]||l2>r)&&(l1<=mid))?p[l1++]:p[l2++];}for(int i=l;i<=r;i++) p[i]=np[i];
}
int main(){freopen("data.in","r",stdin);//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].k=-q[i].a/q[i].b;q[i].pos=i;}sort(q+1,q+n+1);solve(1,n);printf("%.3f",f[n]);return 0;
}