[BZOJ1492/Luogu4027][NOI2007]货币兑换Cash(动态规划,斜率优化,CDQ分治)

发布于 2018-04-08  63 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1492/Luogu4027][NOI2007]货币兑换Cash(动态规划,斜率优化,CDQ分治)

Description

小 Y 最近在一家金券交易所工作。该金券交易所只发行交易两种金券:A 纪念券(以下简称 A 券)和 B 纪念券(以下简称 B 券)。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。
每天随着市场的起伏波动,两种金券都有自己当时的价值,即每一单位金券当天可以兑换的人民币数目。我们记录第 K 天中 A 券和 B 券的价值分别为 AKA_KAK​ 和BKB_KBK​ (元/单位金券)。
为了方便顾客,金券交易所提供了一种非常方便的交易方式:比例交易法。
比例交易法分为两个方面:
a) 卖出金券:顾客提供一个[0,100]内的实数 OP 作为卖出比例,其意义为:将 OP%的 A 券和 OP%的 B 券以当时的价值兑换为人民币;
b) 买入金券:顾客支付 IP 元人民币,交易所将会兑换给用户总价值为IP 的金券,并且,满足提供给顾客的 A 券和 B 券的比例在第 K 天恰好为 RateKRate_KRateK​ ;
例如,假定接下来 3 天内的 AkA_kAk​ 、BkB_kBk​ 、RateKRate_KRateK​ 的变化分别为:
时间 AkA_kAk​ BkB_kBk​ RatekRate_kRatek​
第一天 1 1 1
第二天 1 2 2
第三天 2 2 3
假定在第一天时,用户手中有 100 元人民币但是没有任何金券。
用户可以执行以下的操作:
时间 用户操作 人民币(元) A 券的数量 B 券的数量
开户 无 100 0 0
第一天 买入 100 元 0 50 50
第二天 卖出 50% 75 25 25
第二天 买入 60 元 15 55 40
第三天 卖出 100% 205 0 0
注意到,同一天内可以进行多次操作。
小 Y 是一个很有经济头脑的员工,通过较长时间的运作和行情测算,他已经知道了未来 N 天内的 A 券和 B 券的价值以及 Rate。他还希望能够计算出来,如果开始时拥有 S 元钱,那么 N 天后最多能够获得多少元钱。

Tag

动态规划,斜率优化,CDQ分治

解决思路

题目里面明确提示了必然存在一种最优的买卖方案满足:每次买进操作使用完所有的人民币;每次卖出操作卖出所有的金券。
所以不妨设F[i]表示前i天的最大收益(RMB),那么F[i]可以由之前的某一天j的钱全部换成金券再在这一天换回来。再设X[i]表示第i天的钱全部换成A券的数量和Y[i]表示第i天的钱全部换成B券的数量。
\[F[i]=X[i]*A[i]+Y[i]*B[i]\]
又因为\(\frac{X[i]}{Y[i]}=Rate[i]\),带入解得
\[X[i]=\frac{R[i]*F[i]}{A[i]*R[i]+B[i]} \quad Y[i]=\frac{F[i]}{A[i]*R[i]+B[i]}\]
所以转移方程为
\[F[i]=A[i]*X[j]+B[i]*Y[j]\]
化成斜率形式
\[Y[j]=-\frac{A[i]}{B[i]}*X[j]+\frac{F[i]}{B[i]}\]
由于要最大化截距,所以维护一个凸包。但是,这里不论是斜率还是x都不是递增的,那么有两种维护方式,一种就是splay维护,另一种是CDQ分治。这里使用CDQ分治的方法。
即,每一次分治左右半边,先求左边的答案,然后让左边按照x有序,右边按照斜率k有序。当然大前提一定是在要保证左边的id小于右边的id,这样才能用左边更新右边。那么维护一个左边的凸包,来利用斜率优化更新右边,用一个单调队列就好了。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

#define ll long long
#define ld long double
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=100100;
const ld eps=1e-9;
const ld inf=1e9;

class Data
{
public:
    ld a,b,r,k;
    int id;
};

class Pos
{
public:
    ld x,y;
};

int n;
ld F[maxN];
Data Query[maxN],Q2[maxN];
Pos P[maxN],P2[maxN];
int Stack[maxN];

bool operator < (Pos A,Pos B);
bool operator < (Data A,Data B);
void Divide(int l,int r);
ld Slope(int u,int v);

int main()
{
    int S;
    scanf("%d%d",&n,&S);
    F[0]=S;
    for (int i=1;i<=n;i++)
    {
        scanf("%LF%LF%LF",&Query[i].a,&Query[i].b,&Query[i].r);
        Query[i].k=-Query[i].a/Query[i].b;Query[i].id=i;
    }
    sort(&Query[1],&Query[n+1]);//将点按照斜率排序
    Divide(1,n);
    printf("%.3LF\n",F[n]);
    return 0;
}

bool operator < (Pos A,Pos B){
    if (fabs(A.x-B.x)<=eps) return A.y<B.y+eps;
    else return A.x<B.x+eps;
}

bool operator < (Data A,Data B){
    return A.k<B.k;
}

void Divide(int l,int r)
{
    if (l==r)
    {
        F[l]=max(F[l],F[l-1]);//可能上一个的更优
        P[l].y=F[l]/(Query[l].r*Query[l].a+Query[l].b);//得到(x,y)
        P[l].x=P[l].y*Query[l].r;
        return;
    }
    int mid=(l+r)>>1;
    int p1=l,p2=mid+1;//按照id排序,即原序列中的顺序,注意因为我们在外面已经按照斜率排序了,所以可以保证左边和右边分别斜率递增
    for (int i=l;i<=r;i++)
        if (Query[i].id<=mid) Q2[p1++]=Query[i];
        else Q2[p2++]=Query[i];
    for (int i=l;i<=r;i++) Query[i]=Q2[i];
    //递归处理左半边
    Divide(l,mid);

    int top=0;
    for (int i=l;i<=mid;i++)//构建左边的凸包
    {
        while ((top>=2)&&(Slope(Stack[top],Stack[top-1])<Slope(i,Stack[top])+eps)) top--;
        Stack[++top]=i;
    }

    for (int i=r,j=1;i>=mid+1;i--)//用左边的答案更新右边,由于已经保证右边斜率递增,所以可以直接用一个单调指针,不需要二分了
    {
        while ((j<top)&&(Query[i].k<Slope(Stack[j],Stack[j+1])+eps)) j++;
        F[Query[i].id]=max(F[Query[i].id],P[Stack[j]].x*Query[i].a+P[Stack[j]].y*Query[i].b);
    }
    //递归处理右半边
    Divide(mid+1,r);
    p1=l;p2=mid+1;//由于返回要求按照x排序,所以这里按照x排序
    for (int i=l;i<=r;i++)
        if ((p1<=mid)&&((p2>r)||(P[p1]<P[p2]))) P2[i]=P[p1++];
        else P2[i]=P[p2++];
    for (int i=l;i<=r;i++) P[i]=P2[i];
    return;
}

ld Slope(int u,int v)
{
    if (u==0) return -inf;
    if (v==0) return inf;
    if (fabs(P[u].x-P[v].x)<=eps) return -inf;
    return (P[u].y-P[v].y)/(P[u].x-P[v].x);
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1492/Luogu4027][NOI2007]货币兑换Cash(动态规划,斜率优化,CDQ分治)


HNCJ OIer 一枚