M_sea

洛谷4027 [NOI2007]货币兑换
LuoguBZOJ分析不会做啊qwq以下大部分内容来自 $\mathrm{yyb}$ 的 $\mathrm{blo...
扫描右侧二维码阅读全文
04
2019/04

洛谷4027 [NOI2007]货币兑换

Luogu

BZOJ

分析

不会做啊qwq

以下大部分内容来自 $\mathrm{yyb}$ 的 $\mathrm{blog}$ 。


显然在某一天把钱全部买了,再在后面全部卖掉是最优的。

设 $f[i]$ 表示第 $i$ 天最多有多少 $A$ 券。

那么 $ans=\max\{f[j]\text{全部在第}i\text{天卖掉}\},f[i]=ans\text{全部卖掉}$ 。

这样子就有 $60$ 分了。


考虑斜率优化。

首先有 $ans=\max(f[j]\times a[i]+f[j]/r[j]\times b[i])$ 。

假设 $j$ 比 $k$ 更优,化简后(过程略)得到 $\large-\frac{a[i]}{b[i]}>\frac{\frac{f[j]}{r[j]}-\frac{f[k]}{r[k]}}{f[j]-j[k]}$ 。

左边看成斜率,右边看成直线的两点式,那么每一天都可以对应到一个点 $(f[i],\frac{f[i]}{r[i]})$ ,以及一个斜率 $-\frac{a[i]}{b[i]}$ 。

然而 $f[i]$ 和 $\frac{f[i]}{r[i]}$ 都不单调,于是用平衡树来维护上凸壳就行了。


然而平衡树虽然不要脑子(雾),但是难写的死。

于是可以用 $\mathrm{CDQ}$ 分治来做,具体做法参见 $\mathrm{CDQ}$ 的论文

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

struct node { double a,b,r,k,x,y; int id; } p[N],q[N];
bool operator <(node a,node b) { return a.k>b.k; }

int n,s[N],top=0;
double f[N];

inline double slope(int i,int j) {
    if (!j||fabs(p[i].x-p[j].x)<1e-9) return -1e20;
    return (p[i].y-p[j].y)/(p[i].x-p[j].x);
}

inline void CDQ(int l,int r) {
    if (l==r) {
        f[l]=max(f[l],f[l-1]);
        p[l].y=f[l]/(p[l].a*p[l].r+p[l].b);
        p[l].x=p[l].y*p[l].r;
        return;
    }
    int mid=(l+r)>>1;
    for (re int i=l,j=mid+1,k=l;k<=r;++k) {
        if (p[k].id<=mid) q[i++]=p[k];
        else q[j++]=p[k];
    }
    for (re int k=l;k<=r;++k) p[k]=q[k];
    CDQ(l,mid); top=0;
    for (re int k=l;k<=mid;++k) {
        while (top>1&&slope(s[top-1],s[top])<slope(s[top-1],k)) --top;
        s[++top]=k;
    }
    s[++top]=0; int tmp=1;
    for (re int k=mid+1;k<=r;++k) {
        while (tmp<top&&slope(s[tmp],s[tmp+1])>p[k].k) ++tmp;
        f[p[k].id]=max(f[p[k].id],p[k].a*p[s[tmp]].x+p[k].b*p[s[tmp]].y);
    }
    CDQ(mid+1,r);
    for (re int i=l,j=mid+1,k=l;k<=r;++k) {
        if (((p[i].x<p[j].x)||(fabs(p[i].x-p[j].x)<1e-9&&p[i].y<p[j].y)||j>r)&&i<=mid) q[k]=p[i++];
        else q[k]=p[j++];
    }
    for (re int i=l;i<=r;++i) p[i]=q[i];
}

int main() {
    n=read(),f[0]=read();
    for (re int i=1;i<=n;++i) {
        scanf("%lf%lf%lf",&p[i].a,&p[i].b,&p[i].r);
        p[i].k=-p[i].a/p[i].b,p[i].id=i;
    }
    sort(p+1,p+n+1),CDQ(1,n);
    printf("%.3lf\n",f[n]);
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 35 PM

发表评论