题解 P4027 【[NOI2007]货币兑换】

· · 题解

        思路：首先，我们能想到这道题是一道dp题目，我们设f[i]表示第i天能得到的最大收益，这个最大收益也包括第i天不进行操作的情况下的收益，设X[i]表示第i天将所有的现金都兑换成为金券后能拿到的A券数，Y[i]同理。这是我们发现一个转移式子：f[i]=Max\{f[i-1],A[i]\times X[j]+B[i]\times Y[j]\}\ (1\le j \le i-1)。我们发现这个式子能写成斜率优化的样子：Y[j]=-\frac{A[i]}{B[i]}\times X[j]+\frac{f[i]}{B[i]}。我们考虑一下能否运用斜率优化，好像可以，对于每一个点的斜率k为-\frac{A[i]}{B[i]}，横坐标为X[i]，纵坐标为Y[i]。但是就是有两个不太好的情况，就是每一点的x坐标与斜率k都不单调，这个怎么办？显然用平衡树维护凸包就好了。我们考虑一下不用平衡树能否实现，我们考虑cdq。

​        因为正常的要求最大值的斜率优化都是横坐标单调递增，斜率单调递减，所以我们考虑排序。因为每一个点的斜率都是不变的，即输入之后就是定下来的，所以我们可以将这些所有的点都按照斜率递减排序，但是这样就不是按照天数递增的顺序了，所以我们就不能直接运用排序后的顺序来处理这些点。我们将天数进行分治，这样的话我们每一个点就需要再存一个参数，即天数的编号。

        因为这是dp，所以我们在递归左区间之后显然要先处理影响，再递归右区间。现在考虑怎么处理影响。

​        因为我们每一次处理影响之前都已经处理好左区间了，所以我们现在可以不用理会左区间的具体顺序了，这样的话我们就能对其进行任意顺序的处理，我们可以将左区间的这些点按照横坐标排序，这样我们就能够达到上面所提出的目的，也就是把点按照顺序插入到凸包里面。因为我们是用左区间来更新右区间，所以我们不用去管右区间，并且因为右区间的斜率是单调递减的，所以我们可以按照右区间原本的顺序来进行更新。

​        我们在递归出口的地方不能就是直接return，我们需要做一些小小的处理，因为我们在return 之前这个点一定已经做完前面的点的所有更新了，但是没有进行不作处理的更新，所以f[i]=Max\{f[i],f[i-1]\}。至此搜有的更新都完成了，这是就可以了处理当前点的横纵坐标。因为必然存在一种最优的买卖方案满足：每次买进操作使用完所有的人民币；每次卖出操作卖出所有的金券，所以当前点的横纵坐标就是X[i]=\frac{f[i]}{A[i]*Rate[i]+B[i]}\times A[i]，Y[i]=\frac{f[i]}{A[i]*Rate[i]+B[i]}。

​        对于横坐标排序，我们显然没有必要每一次都用sort，我们运用归并排序的思想，直接排序即可，时间复杂度会降下O(log_n)。

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100010
#define eps 1e-9
int n,que[N];double f[N];
struct Node {double a,b,rate,k,x,y;int id;}node[N],tmp[N];
bool cmp(const Node &a,const Node &b) {return a.k>b.k;}
double re_x(int i) {return node[i].x;}
double re_y(int i) {return node[i].y;}
double re_k(int i,int j)
{
    if(fabs(node[i].x-node[j].x)<eps)return 1e20;
    return (re_y(j)-re_y(i))/(re_x(j)-re_x(i));
}
void solve(int l,int r)
{
    if(l==r)
    {
        f[l]=max(f[l],f[l-1]);
        node[l].y=f[l]/(node[l].a*node[l].rate+node[l].b);
        node[l].x=node[l].y*node[l].rate;return;
    }
    int mid=(l+r)>>1,tl=l-1,tr=mid;
    for(int i=l;i<=r;i++) (node[i].id<=mid)?tmp[++tl]=node[i]:tmp[++tr]=node[i];
    for(int i=l;i<=r;i++) node[i]=tmp[i];solve(l,mid);
    int L=1,R=0;
    for(int i=l;i<=mid;i++)
        {while(R>1&&re_k(que[R],que[R-1])<re_k(que[R],i)+eps) R--;que[++R]=i;}
    for(int i=mid+1;i<=r;i++)
    {
        while(L<R&&re_k(que[L],que[L+1])+eps>node[i].k) L++;
        f[node[i].id]=max(f[node[i].id],node[que[L]].x*node[i].a+node[que[L]].y*node[i].b);
    }solve(mid+1,r),tl=l,tr=mid+1;
    for(int i=l;i<=r;i++)
    {
        if((node[tl].x<node[tr].x||tr>r||fabs(node[tl].x-node[tr].x)<eps)&&tl<=mid)
            tmp[i]=node[tl++];
        else tmp[i]=node[tr++];
    }
    for(int i=l;i<=r;i++) node[i]=tmp[i];
}
int main()
{
    scanf("%d%lf",&n,&f[0]);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf%lf",&node[i].a,&node[i].b,&node[i].rate);
        node[i].k=-node[i].a/node[i].b,node[i].id=i;
    }sort(node+1,node+n+1,cmp),solve(1,n),printf("%.3lf\n",f[n]);
}