【BZOJ】1492: [NOI2007]货币兑换Cash

【题意】初始资金s，有两种金券A和B，第i天，买入时将投入的资金购买比例为rate[i]的两种股票，卖出时将持有的一定比例的两种股票卖出，第i天股票价格为A[i],B[i]，求最大获利。n<=100000。

【算法】动态规划+斜率优化（CDQ分治）

【题解】为了最大获利，每次交易一定是全部买进和全部卖出。

令s[i]表示前i天的最大获利，f[i]表示第i天能购买的最多A股数，g[i]=f[i]/rate[i]表示第i天能购买的最多B股数。

s[i]=max{ s[i-1] , f[j]*A[i]+g[j]*B[i] }，j<i。

g[i]=s[i]/(A[i]*rate[i]+B[i])

f[i]=g[i]*rate[i]

对于决策j和k，假设f[j]<f[k]，当k优于j时有：

f[j]*A[i]+g[j]*B[i]<f[k]*A[i]+g[k]*B[i]

移向得(g[j]-g[k])/(f[j]-f[k])>-A[i]/B[i]，令k[i]=-A[i]/B[i]，所以：

对于满足f[j]<f[k]的决策j和k，满足(g[j]-g[k])/(f[j]-f[k])>k[i]时决策k优于决策j。

然后用CDQ分治维护动态上凸包，按阶段分治，左子区间按x[]排序构造凸包，右子区间按k[]排序顺序决策。

具体过程见：CDQ分治优化动态规划

复杂度O(n log n)。

#include<cstdio>

#include<cstring>

#include<cctype>

#include<cmath>

#include<algorithm>

using namespace std;

const int maxn=;

const double eps=1e-,inf=;

double s[maxn];

int n,st[maxn];

struct cyc{int id;double A,B,r,k,x,y;}a[maxn],b[maxn];

bool cmp(cyc a,cyc b){return a.k>b.k;}

double k(int A,int B){

    if(fabs(a[A].x-a[B].x)<eps){if(a[B].y<a[A].y)return -inf;else return inf;}

    return (a[A].y-a[B].y)/(a[A].x-a[B].x);

}

void CDQ(int l,int r){

    if(l==r){

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

        a[l].y=s[l]/(a[l].A*a[l].r+a[l].B);

        a[l].x=a[l].y*a[l].r;

        return;

    }

    int mid=(l+r)>>;

    int x1=l-,x2=mid;

    for(int i=l;i<=r;i++)if(a[i].id<=mid)b[++x1]=a[i];else b[++x2]=a[i];

    for(int i=l;i<=r;i++)a[i]=b[i];

    CDQ(l,mid);

    int top=;

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

        while(top>&&k(st[top],i)>k(st[top-],st[top]))top--;

        st[++top]=i;

    }

    int x=;

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

        while(x<top&&k(st[x],st[x+])>a[i].k)x++;

        s[a[i].id]=max(s[a[i].id],a[st[x]].x*a[i].A+a[st[x]].y*a[i].B);

    }

    CDQ(mid+,r);

    x1=l,x2=mid+;

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

        if(x1>mid)b[i]=a[x2++];else

        if(x2>r)b[i]=a[x1++];else

        if(a[x1].x<a[x2].x)b[i]=a[x1++];else b[i]=a[x2++];

    }

    for(int i=l;i<=r;i++)a[i]=b[i];

}

int main(){

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

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

        a[i].id=i;

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

        a[i].k=-a[i].A/a[i].B;

    }

    sort(a+,a+n+,cmp);

    CDQ(,n);

    printf("%.3lf",s[n]);

    return ;

}