[bzoj1492][NOI2007]Cash[CDQ分治；dp；斜率优化]

首先，设f[x]表示x天能获得的A券最大值，有动规方程：

　　$f[i]=max\{f[j]*A[i]+f[j]*B[i]/R[j]\}*R[i]/(R[i]*A[i]+B[i])$，

　　设 $j<k$ ,$f[j]>f[k]$

　　$\Rightarrow (f[j]/R[j]-f[k]/R[k])/(f[j]-f[k]) \leftarrow A[i]/B[i]$

　　令$g[i]=f[i]/R[i]$，则有$(g[j]-g[k])/(f[j]-f[k]) \leftarrow A[i]/B[i]$

　　将每一天描述为一个点$(f[i],g[i])$可以在一个上凸壳上进行二分进行斜率优化。

　　CDQ分治中按f[x]排序，分治时按id分割，这样用一个凸壳从左向右扫一遍，就可以更新整个区间的答案。

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <cmath>

 #include <ctime>

 using namespace std;

 struct node

 {

     double    x,y,A,B,R,k; int    pos;

     bool    operator<(const node temp)const { return k>temp.k; }

 }c[],temp[];

 int    n,head,tail,H[];

 double    f[];

 const double    eps=1e-;

 double    Calc(const int x,const int y)

 {

     if(fabs(c[x].x-c[y].x)<eps)return 1e100;

     return (c[x].y-c[y].y)/(c[x].x-c[y].x);

 }

 void    CDQ(const int l,const int r)

 {

     if(l==r)

     {

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

         c[l].y=f[l]/(c[l].R*c[l].A+c[l].B);c[l].x=c[l].y*c[l].R;

         return ;

     }

     int    i,mid=l+((r-l)>>);

     int    l1=l,l2=mid+;

     for(i=l;i<=r;++i)

     {

         if(c[i].pos<=mid)temp[l1++]=c[i];

         else    temp[l2++]=c[i];

     }

     for(i=l;i<=r;++i)c[i]=temp[i];

     CDQ(l,mid);

     tail=,head=;

     for(i=l;i<=mid;++i)

     {

         while(tail> && Calc(H[tail-],H[tail])<Calc(H[tail],i))tail--;

         H[++tail]=i;

     }

     for(i=mid+;i<=r;++i)

     {

         while(head<tail && Calc(H[head],H[head+])>c[i].k)head++;

         f[c[i].pos]=max(f[c[i].pos],c[H[head]].x*c[i].A+c[H[head]].y*c[i].B);

     }

     CDQ(mid+,r);

     l1=l;l2=mid+;

     for(i=l;i<=r;++i)

     {

         if((c[l1].x<c[l2].x || (fabs(c[l1].x-c[l2].x)<eps && c[l1].y<c[l2].y+eps) || l2>r) && l1<=mid)

             temp[i]=c[l1++];

         else

             temp[i]=c[l2++];

     }

     for(i=l;i<=r;++i)c[i]=temp[i];

     return ;

 }

 int main()

 {

     scanf("%d%lf",&n,&f[]);

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

     {

         scanf("%lf%lf%lf",&c[i].A,&c[i].B,&c[i].R);

         c[i].k=-c[i].A/c[i].B;c[i].pos=i;

     }

     sort(c+,c+n+);

     CDQ(,n);

     printf("%.3f\n",f[n]);

     return ;

 }