【BZOJ1492】[NOI2007]货币兑换Cash

2015.08.10 10:17 Mon | 22次阅读 | 旧日oi | 固定链接 | 源码

Description

表示语死早

题解

首先转移方程,dp[i]表示前i天能获得的最大钱数。 这不就和开始给出的形式完全一样嘛。 令x[i]=a[i]后面那坨东西,y[i]=b[i]后面那坨东西。 公式转化为 y[j]=-a[i]/b[i]*x[j]+dp[i]/bi 求这些直线的最小截距。 其中-a[i]/b[i](也就是斜率k)不单调,x[i]也不单调。 于是怎么搞?
我们以x[j]为键值建一颗splay来搞。 对于一个要插入的点i,查寻它应该插在某两个点之间,或者是这个点没用,或者是直接能替换掉另一个点。 然后把点i splay到根。 然后删掉它左边和右边的不满足下凸性质的点(一定是和点i相邻的一段点) 然后处理这个点和左右的点的斜率。 查询的话二分查一下就行了。 嗯,就是这样了,代码长度3k,不虚不虚,单纵就是干!

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 100005
#define inf 233333333
#define ls(t) tr[t].ls
#define x(t) tr[t].x
#define y(t) tr[t].y
#define rs(t) tr[t].rs
#define fa(t) tr[t].fa
#define lk(t) tr[t].lk
#define rk(t) tr[t].rk
int cnt;
int n,root;
double a[N],b[N],r[N],dp[N];
struct node
{
    int ls,rs,fa;
    double lk,rk,x,y;
}tr[N];
double calc(int x)
{return dp[x]/(r[x]*a[x]+b[x]);}
double calc_k(double a,double b,double c,double d)
{
    return a==c?inf:(b-d)/(a-c);
}
int find(double k)
{
    for(int x=root;x;)
    {
        if(lk(x)<k) x=ls(x);
        else if(rk(x)>k) x=rs(x);
        else return x;
    }
}
int merge(int x,int y)
{
    int i=x;
    for(;rs(i);i=rs(i));
    rs(i)=y;fa(y)=i;
    return x;
}
void update()
{
    int t=root;
    if(!ls(t))
    {
        lk(t)=inf;
        rk(t)=lk(rs(t))=calc_k(x(t),y(t),x(rs(t)),y(rs(t)));
    }
    if(!rs(t))
    {
        rk(t)=-inf;
        lk(t)=rk(ls(t))=calc_k(x(t),y(t),x(ls(t)),y(ls(t)));
    }
    if(ls(t)&&rs(t))
    {
        rk(t)=lk(rs(t))=calc_k(x(t),y(t),x(rs(t)),y(rs(t)));
        lk(t)=rk(ls(t))=calc_k(x(t),y(t),x(ls(t)),y(ls(t)));
        if(lk(t)<=rk(t))
        {
            root=merge(ls(t),rs(t));fa(root)=0;
            rk(root)=lk(rs(root))=calc_k(x(root),y(root),x(rs(root)),y(rs(root)));
        }
    }
}
bool is(int x)
{
    return rs(fa(x))==x;
}
void link(int x,int y,int d)
{
    fa(x)=y;
    if(d) rs(y)=x;
    else ls(y)=x;
}
void rotate(int x)
{
    int y=fa(x),z=fa(y),id=is(x),t=id?ls(x):rs(x);
    link(x,z,is(y));link(t,y,id);link(y,x,!id);
    fa(0)=ls(0)=rs(0)=0;
}
void splay(int x,int g)
{
    int y,z;
    while(fa(x)!=g)
    {
        y=fa(x);z=fa(y);
        if(z==g)
        {
            rotate(x);
            break;
        }
        rotate(is(y)==is(x)?y:x);rotate(x);
    }
    if(!g) root=x,fa(x)=0;
}
int workl()
{
    int x,i;
    for(i=ls(root);i;)
    {
        if(calc_k(x(i),y(i),x(root),y(root))<lk(i)) x=i,i=rs(i);
        else i=ls(i);
    }
    return x;
}
int workr()
{
    int x,i;
    for(i=rs(root);i;)
    {
        if(calc_k(x(i),y(i),x(root),y(root))>rk(i)) x=i,i=ls(i);
        else i=rs(i);
    }
    return x;
}
void insert(int t)
{
    y(t)=calc(t);x(t)=y(t)*r[t];
    int i,flag;
    for(i=root;i;)
    {
        if(x(i)<x(t)) flag=i,i=rs(i);
        else if(x(i)>x(t)) flag=i,i=ls(i);
        else if(y(i)>y(t)) return;
        else {y(i)=y(t);t=i;break;}
    }
    if(!i)
    {
        if(x(flag)<x(t)) rs(flag)=t;
        else ls(flag)=t;
    }
    if(!i) fa(t)=flag;      
    splay(t,0);
    if(ls(t))
    {
        flag=workl();
        splay(flag,root);
        rs(flag)=0;
    }
    if(rs(t))
    {
        flag=workr();
        splay(flag,root);
        ls(flag)=0;
    }
    update();
}
int main()
{
    cin>>n>>dp[1];root=1;
    for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&a[i],&b[i],&r[i]);
    y(1)=calc(1);x(1)=y(1)*r[1];
    lk(1)=inf;rk(1)=-inf;
    for(int i=2;i<=n;i++)
    {
        int j=find(-a[i]/b[i]);
        dp[i]=max(dp[i-1],a[i]*x(j)+b[i]*y(j));
        insert(i);
    }
    printf("%.3lf",dp[n]);
}```