loj2353. 「NOI2007」 货币兑换

链接

https://loj.ac/problem/2353

思路

题目不重要，重要的是最后一句话

提示
必然存在一种最优的买卖方案满足：每次买进操作使用完所有的人民币；每次卖出操作卖出所有的金券。

所以f[i]表示第i天最大收益
设第i天把m元换成券（A券rate[i]*x个，B券x个），则\(a[i]*rate[i]*x+b[i]*x=m\)
\(x=\frac{m}{a[i]*rate[i]+b[i]}\)就可以算出来A券和B券了
根据提示，就可以把一天的所有钱都换掉
设x[j]=f[j]换成A券个数，y[j]=f[j]换成B券的个数（他们只跟j有关）
\(f[i]=a[i]*x[j]+b[i]*y[j]\)
\(\frac{f[i]}{b[i]}=\frac{a[i]}{b[i]}*x[j]+y[j]\)
\(y[j]=-\frac{a[i]}{b[i]}*x[j]+\frac{f[i]}{b[i]}\)
cdq进行dp维护凸包

代码

#include <bits/stdc++.h>
using namespace std;
const double eps=1e-9;
const int N=2e5+7;
int n,stak[N];
struct node {
    double a,b,rate,k,x,y;
    int id;
    bool operator < (const node &b) const {
        return k>b.k;
    }
}p[N],t[N];
double f[N];
double get_k(int a,int b) {
    if(!b) return -1e20;
    if(fabs(p[a].x-p[b].x)<eps) return 1e20;
    return (p[b].y-p[a].y)/(p[b].x-p[a].x);
}
void cdq(int l,int r) {
    if(l==r) {
        f[l]=max(f[l],f[l-1]); 
        p[l].x=p[l].rate*(f[l]/(p[l].a*p[l].rate+p[l].b));
        p[l].y=f[l]/(p[l].a*p[l].rate+p[l].b);
        return;
    }
    int mid=(l+r)>>1;
    int l1=l,l2=mid+1;
    for(int i=l;i<=r;++i) {//sort p according to id 
        if(p[i].id<=mid) t[l1++]=p[i];
        else t[l2++]=p[i];
    }
    for(int i=l;i<=r;++i) p[i]=t[i];
    cdq(l,mid);//solve left half
    int top=0;
    for(int i=l;i<=mid;++i) {
        while(top>1&&get_k(stak[top-1],stak[top])<get_k(stak[top-1],i)+eps) top--;
        stak[++top]=i;
    }//get the upper convex hull
    stak[++top]=0;
    int j=1;
    for(int i=mid+1;i<=r;++i) {
        while(j<top&&get_k(stak[j],stak[j+1])+eps>p[i].k) j++;
        f[p[i].id]=max(f[p[i].id],p[i].a*p[stak[j]].x+p[i].b*p[stak[j]].y);
    }//use left hull to update right ans
    cdq(mid+1,r);//continue
    l1=l,l2=mid+1;
    for(int i=l;i<=r;++i) {//sort p according to x
        if(((p[l1].x<p[l2].x||(fabs(p[l1].x-p[l2].x)<eps&&p[l1].y<p[l2].y)||l2>r))&&l1<=mid)
            t[i]=p[l1++];
        else
            t[i]=p[l2++];
    }
    for(int i=l;i<=r;++i) p[i]=t[i];
}
int main() {
    scanf("%d%lf",&n,&f[0]);
    for(int i=1;i<=n;++i) {
        scanf("%lf%lf%lf",&p[i].a,&p[i].b,&p[i].rate);
        p[i].k=-p[i].a/p[i].b;
        p[i].id=i;
    }    
    sort(p+1,p+1+n);    
    cdq(1,n);
    printf("%.3lf",f[n]);
    return 0;
}