BZOJ3963 WF2011MachineWorks（动态规划+斜率优化+cdq分治）

　　按卖出时间排序后，设f[i]为买下第i台机器后的当前最大收益，则显然有f[i]=max{f[j]+g_j*(d_i-d_j-1)+r_j-p_i}，且若此值<0，应设为-inf以表示无法购买第i台机器。

　　考虑优化，显然是一个斜率优化式子，设j转移优于k，则f[j]+g_j(d_i-d_j-1)+r_j>f[k]+g_k(d_i-d_k-1)+r_k，移项得(f[j]-g_jd_j-g_j+r_j)-(f[k]-g_kd_k-g_k+r_k)>d_i(g_k-g_j)。g没有单调性，于是cdq分治，按g排序建上凸壳即可。

　　注意比较斜率时只能用long double，因为乘法会溢出。对于横坐标相同的点需要特判一下，如果加进去的点纵坐标较大就把之前的点弹掉。感觉每次写斜率优化对这种问题都毫无办法。复杂度O(nlogn)。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 100010

#define inf 2000000000000000000ll

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int T,n,m,k,q[N];

struct data

{

    int d,p,r,g,i;ll ans;

    bool operator <(const data&a) const

    {

        return d<a.d;

    }

}a[N],b[N];

ll calc(int i){return a[i].ans-1ll*a[i].g*(a[i].d+)+a[i].r;}

bool check(int x,int y,int i)

{

    if (a[i].g==a[y].g) return calc(i)>=calc(y);

    return (long double)(calc(i)-calc(y))/(a[i].g-a[y].g)>=(long double)(calc(y)-calc(x))/(a[y].g-a[x].g);

}

void solve(int l,int r)

{

    if (l>=r) return;

    int mid=l+r>>;

    solve(l,mid);

    int head=,tail=;

    for (int i=l;i<=mid;i++)

    {

        while (tail>&&check(q[tail-],q[tail],i)) tail--;

        q[++tail]=i;

    }

    for (int i=mid+;i<=r;i++)

    {

        while (head<tail&&calc(q[head+])-calc(q[head])>-1ll*a[i].d*(a[q[head+]].g-a[q[head]].g)) head++;

        if (calc(q[head])+1ll*a[q[head]].g*a[i].d-a[i].p>=)

        a[i].ans=max(a[i].ans,calc(q[head])+1ll*a[q[head]].g*a[i].d-a[i].p);

    }

    solve(mid+,r);

    int i=l,j=mid+;

    for (int k=l;k<=r;k++)

    if (i<=mid&&a[i].g<a[j].g||j>r) b[k]=a[i++];

    else b[k]=a[j++];

    for (int k=l;k<=r;k++) a[k]=b[k];

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj3963.in","r",stdin);

    freopen("bzoj3963.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read(),k=read();

    while (n)

    {

        for (int i=;i<=n;i++) a[i].d=read(),a[i].p=read(),a[i].r=read(),a[i].g=read(),a[i].i=i;

        n++,a[n].d=k+,a[n].p=a[n].r=a[n].g=;

        sort(a+,a+n+);

        for (int i=;i<=n;i++) a[i].ans=-inf;a[].ans=m;

        solve(,n);

        for (int i=;i<=n;i++) a[].ans=max(a[].ans,a[i].ans);

        printf("Case ");printf("%d",++T);printf(": ");printf(LL,a[].ans);

        n=read(),m=read(),k=read();

    }

    return ;

}

巴特西

BZOJ3963 WF2011MachineWorks（动态规划+斜率优化+cdq分治）

最新文章

热门文章