BZOJ1492:[NOI2007]货币兑换Cash 斜率优化+cdq分治

思路:

我才发现自己以前写的模板多么傻逼.现在的模板总算是科学了.

不得不说cdq分治还是过于强大了OTZ.

另外等号问题只有在对拍的时候才能改过来了?实在不懂为什么要加一个等号.

(另外实数的手写读入丧心病狂)

#include<cmath>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef double f2;
 
namespace Fio{
    inline int getc(){
        static const int L=1<<15;static char buf[L],*S=buf,*T=buf;
        if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
        return*S++;
    }
    template<typename T>inline void Getint(T&x){
        int c;while(!isdigit(c=getc())&&c!='-');bool sign=c=='-';
        x=sign?0:c-'0';while(isdigit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
        if(sign)x=-x;
    }
    template<typename T>inline void Getfloat(T&x){
        int c;while(!isdigit(c=getc())&&c!='-');bool sign=c=='-';
        x=sign?0:c-'0';while(isdigit(c=getc()))x=10*x+c-'0';
        if(c=='.'){double f=0.1;while(isdigit(c=getc()))x+=f*(c-'0'),f/=10;}
        if(sign)x=-x;
        if(fabs(x)<1e-8)x=0;
    }
}
 
#define N 100010
 
f2 f[N],A[N],B[N],na[N],nb[N],Rat[N];
 
int seq[N],ins[N];
bool cmp(const int&a,const int&b){return -A[a]*B[b]>-A[b]*B[a];}
 
int q[N],qq[N],stk[N],top;
inline void Solve(int l,int r){
    if(l==r){
        f[q[l]]=max(f[q[l]],f[q[l]-1]);
        nb[q[l]]=f[q[l]]/(A[q[l]]*Rat[q[l]]+B[q[l]]),na[q[l]]=nb[q[l]]*Rat[q[l]];
        return;
    }
     
    int mid=(l+r)>>1;
    register int i,j,k;
    int p1=l,p2=mid+1;for(i=l;i<=r;++i)if(q[i]<=mid)qq[p1++]=q[i];else qq[p2++]=q[i];
    memcpy(q+l,qq+l,(r-l+1)*sizeof(int));
     
    Solve(l,mid);
     
    for(top=0,i=l;i<=mid;++i){
        while(top>1&&(nb[q[i]]-nb[stk[top]])*(na[stk[top]]-na[stk[top-1]])>=(nb[stk[top]]-nb[stk[top-1]])*(na[q[i]]-na[stk[top]]))--top;
        stk[++top]=q[i];
    }
     
    j=mid+1;
    for(i=1;i<=top;++i)
        while(j<=r&&(i==top||((-A[q[j]]/B[q[j]])*(na[stk[i+1]]-na[stk[i]])>=nb[stk[i+1]]-nb[stk[i]])))f[q[j]]=max(f[q[j]],A[q[j]]*na[stk[i]]+B[q[j]]*nb[stk[i]]),++j;
     
    Solve(mid+1,r);
     
     
    for(i=k=l,j=mid+1;i<=mid&&j<=r;)qq[k++]=na[q[i]]<na[q[j]]?q[i++]:q[j++];
    while(i<=mid)qq[k++]=q[i++];
    while(j<=r)qq[k++]=q[j++];
    memcpy(q+l,qq+l,(r-l+1)*sizeof(int));
}
 
int main(){
    int n;Fio::Getint(n),Fio::Getfloat(f[1]);
    register int i,j;for(i=1;i<=n;++i)Fio::Getfloat(A[i]),Fio::Getfloat(B[i]),Fio::Getfloat(Rat[i]);
    /*int n;scanf("%d%lf",&n,&f[1]);
    register int i,j;for(i=1;i<=n;++i)scanf("%lf%lf%lf",&A[i],&B[i],&Rat[i]);*/
     
    for(i=1;i<=n;++i)q[i]=i;sort(q+1,q+n+1,cmp);
     
    Solve(1,n);
    printf("%.3lf",f[n]);   
    return 0;
}