BZOJ-1492: [NOI2007]货币兑换Cash

Description

小Y最近在一家金券交易所工作。该金券交易所只发行交易两种金券：A纪念券（以下简称A券）和 B纪念券（以下简称B券）。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。每天随着市场的起伏波动，两种金券都有自己当时的价值，即每一单位金券当天可以兑换的人民币数目。我们记录第 K 天中 A券 和 B券 的价值分别为 AK 和 BK（元/单位金券）。为了方便顾客，金券交易所提供了一种非常方便的交易方式：比例交易法。比例交易法分为两个方面：（a）卖出金券：顾客提供一个 [0,100] 内的实数 OP 作为卖出比例，其意义为：将 OP% 的 A券和 OP% 的 B券 以当时的价值兑换为人民币；（b）买入金券：顾客支付 IP 元人民币，交易所将会兑换给用户总价值为 IP 的金券，并且，满足提供给顾客的A券和B券的比例在第 K 天恰好为 RateK。注意到，同一天内可以进行多次操作。小Y是一个很有经济头脑的员工，通过较长时间的运作和行情测算，他已经知道了未来N天内的A券和B券的价值以及Rate。他还希望能够计算出来，如果开始时拥有S元钱，那么N天后最多能够获得多少元钱。
必然存在一种最优的买卖方案满足：
每次买进操作使用完所有的人民币；每次卖出操作卖出所有的金券。n<=10^5

设dp[i]表示前i天能得到的最多的钱，枚举买入时间，进行转移，复杂度O(n^2)
设买进的A劵为Rate*x单位，B劵为x单位，那么dp[i]=max{dp[j]+Rate*x*AKi+x*BKi}
等价于过点(-x,Rate*x)斜率为在y轴的截距乘以AKi，转化为求前缀凸包，每次二分找切点优化DP。
平衡树维护凸包，或者是CDQ分治都可以。复杂度nlogn

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000 
#define eps 1e-10 
#define inf 1e9 
// c[j]=f[j]*r[j]/(a[j]*r[j]+b[j]);
// d[j]=f[j]/(a[j]*r[j]+b[j]);
// f[i]=max{c[j]*a[i]+d[j]*b[i]}
// c[j]=(-b[i]/a[i])*d[j]+f[i]/a[i]

int n,t[N],cg[N],z[N];
struct node
{
    double a,b,r,c,d,f,k;
}a[N];
bool cmp(int x,int y){return a[x].k>a[y].k;}
double getk(int x,int y)
{
    if(fabs(a[x].d-a[y].d)<eps) return inf;
    return (a[x].c-a[y].c)/(a[x].d-a[y].d);
}

void solve(int l,int r)
{
    if(l==r)
    {
        a[l].f=max(a[l].f,a[l-1].f);
        a[l].d=a[l].f/(a[l].a*a[l].r+a[l].b);
        a[l].c=a[l].d*a[l].r;
        return ;
    }
    int mid=(l+r)>>1; int i,i1=l,i2=mid+1;
    for(i=l;i<=r;++i)
    {
        if(t[i]<=mid) cg[i1++]=t[i];
        else cg[i2++]=t[i];
    }
    for(i=l;i<=r;++i) t[i]=cg[i];
    solve(l,mid);
    int top=0;
    for(i=l;i<=mid;++i)
    {
        while(top>1&&getk(z[top-1],z[top])<getk(z[top],t[i])+eps) top--;
        z[++top]=t[i];
    }
    for(i1=1,i=mid+1;i<=r;++i)
    {
        while(i1<top&&getk(z[i1],z[i1+1])+eps>a[t[i]].k) ++i1;
        a[t[i]].f=max(a[t[i]].f,a[z[i1]].c*a[t[i]].a+a[z[i1]].d*a[t[i]].b);
    }
    solve(mid+1,r);
    for(i1=l,i2=mid+1,i=l;i<=r;++i)
    {
        if(i2>r||(i1<=mid&&(fabs(a[t[i1]].d-a[t[i2]].d)<eps ? 
            a[t[i1]].c<a[t[i2]].c : a[t[i1]].d<a[t[i2]].d ))) cg[i]=t[i1++];
        else cg[i]=t[i2++];
    }
    for(i=l;i<=r;++i) t[i]=cg[i];
}

int main()
{
    scanf("%d%lf",&n,&a[1].f);
    for(int i=1;i<=n;++i)
    {
        scanf("%lf%lf%lf",&a[i].a,&a[i].b,&a[i].r);
        t[i]=i; a[i].k=-a[i].b/a[i].a;
    }
    sort(t+1,t+n+1,cmp);
    solve(1,n);
    printf("%.3lf",a[n].f);
    return 0;
}