BZOJ 1492 [NOI2007]货币兑换Cash (CDQ分治/splay 维护凸包)

题目大意：太长了略

splay调了两天一直WA弃疗了

首先，我们可以猜一个贪心，如果买/卖，就一定都买/卖掉，否则不买/卖

反正货币的行情都是已知的，没有任何风险，所以肯定要选择最最最优的方案了

容易得到方程

$dp[i]=max(dp[i-1],a[i]*\frac{dp[j]*rate[j]}{rate[j]*a[j]+b[j]}+b[i]*\frac{dp[j]}{rate[j]*a[j]+b[j]})$

显然是要用凸优化了

splay非常无脑，splay维护此题的凸包，需要找前驱，删前驱，找后继，删后继，一大堆特判...绝对恶心到吐

所以这是一篇$CDQ$分治题解

令$x=\frac{dp[j]}{rate[j]*a[j]+b[j]},y=x*rate[j]$

移项，可得

$dp[i]-b[i]*x=a[i]*y$

$y=\frac{dp[i]}{a[i]}-\frac{b[i]}{a[i]}x$

发现斜率$k=-\frac{b[i]}{a[i]}$是一定的，我们在外层把斜率k从小到大排序，可以优化掉一个$log$，递归时按$x$从小到大排序

这样，递归时，每一层内部都是按$k$有序的，把这一层按照时间分为左右两个部分(不要破坏$k$的有序状态)

先递归处理左半个区间，回溯后，左半部分的答案已知，且不会被右半部分的答案所影响

且左半部分按$x$从小到大排序，右半部分按斜率$k$从小到大排序，取最小值，由于$k<0$，用单调栈维护一个上凸包即可

处理完了左边对右边的贡献，递归处理右半部分

回溯时，先处理$dp[i]=dp[i-1]$的情况，再按$x$排序，回溯到上一层

 #include <cmath>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N1 101000

 #define M1 205

 #define ll long long

 #define dd double

 #define uint unsigned int

 #define inf 233333333

 #define il inline

 using namespace std;

 const dd eps=(1e-);

 int n,m;

 int stk[N1];

 dd A[N1],B[N1],r[N1],X[N1],Y[N1],K[N1],f[N1];

 //struct node{dd x,y,k,ans;int id;};

 int cmp1(int s1,int s2){return K[s1]-K[s2]<;}

 int id[N1],tmp[N1];

 dd get_slope(int s1,int s2){

     if(!s2) return inf;

     return (Y[s1]-Y[s2])/(X[s1]-X[s2]);

 }

 void CDQ(int L,int R)

 {

     if(R-L<=) return;

     int M=(L+R)>>;

     int tp=,i,j,pl=L,pr=M,k,cnt;

     for(int i=L;i<R;i++)

         if(id[i]<M) tmp[pl++]=id[i];

         else tmp[pr++]=id[i];

     for(int i=L;i<R;i++)

         id[i]=tmp[i];

     CDQ(L,M);

     for(i=L;i<M;i++)

     {

         k=id[i];

         if(tp>&&fabs(X[stk[tp]]-X[k])<eps&&Y[k]-Y[stk[tp]]<eps) continue;

         while(tp>&&get_slope(stk[tp],stk[tp-])<=get_slope(k,stk[tp-]))

             tp--;

         stk[++tp]=k;

     }

     for(i=M;i<R;i++)

         f[i]=max(f[i-],f[i]);

     for(i=M;i<R;i++)

     {

         while(tp>&&get_slope(stk[tp],stk[tp-])<=K[id[i]])

             tp--;

         k=id[i],j=stk[tp];

         f[k]=max(f[k],A[k]*Y[j]+B[k]*X[j]);

         X[k]=f[k]/(A[k]*r[k]+B[k]);

         Y[k]=r[k]*X[k];

     }

     CDQ(M,R);

     i=L,cnt=L,j=M;

     while(i<M&&j<R){

         if(X[id[i]]<X[id[j]])

             tmp[cnt++]=id[i],i++;

         else

             tmp[cnt++]=id[j],j++;

     }

     while(i<M) tmp[cnt++]=id[i],i++;

     while(j<R) tmp[cnt++]=id[j],j++;

     for(i=L;i<R;i++)

         id[i]=tmp[i],f[id[i]]=max(f[id[i]],f[id[i]-]);

 };

 dd S;

 int main()

 {

     //freopen("t1.in","r",stdin);

     scanf("%d%lf",&n,&S);

     for(int i=;i<=n;i++)

     {

         scanf("%lf%lf%lf",&A[i],&B[i],&r[i]);

         K[i]=-B[i]/A[i];id[i]=i;

     }

     f[]=S,X[]=S/(A[]*r[]+B[]),Y[]=X[]*r[];

     sort(id+,id+n+,cmp1);

     CDQ(,n+);

     dd ans=;

     for(int i=;i<=n;i++)

         ans=max(ans,f[i]);

     printf("%.3lf\n",ans);

     return ;

 }

巴特西

BZOJ 1492 [NOI2007]货币兑换Cash (CDQ分治/splay 维护凸包)

最新文章

热门文章