BZOJ3963 Machine Works

lgswdn_SA · 2021-08-07 21:22:34 · 题解

不懂啊我自认为我说的挺详细的。

考虑 DP 转移方程（已经按时间排过序）。

稍微转化一下。

每个点转化成 (g_j,f_j-p_j+r_k-g_jd_j-g_j)，即用考虑斜率 -d_i 的直线去切这些点，于是 cdq 分治维护上凸壳，用单调队列弄转移即可。

具体维护就是，先按照 d 排序，然后 cdq 先分治处理左半边的东西，弄完后按照 x 坐标（即 d）排序，之后左半部分的点求出来一个凸包，注意到右半部分的斜率是有序的，于是直接单调队列去求解即可，随后再去分治右半部分。

记得要注意取等条件啊，因为在比较斜率的地方没取等调了一个晚上 /px。

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int N=1e5+9;
const __int128 l1=1;

inline long long read() {
    register long long x=0, f=1; register char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
    return x*f;
}

int n,c,m,f[N],q[N];

struct node {int id,d,p,r,g,y;} a[N],tmp[N];
bool cmpd(const node &x,const node &y) {return x.d<y.d;}
bool cmpg(const node &x,const node &y) {return x.g==y.g?x.y>y.y:x.g<y.g;}

bool cmp(node &a,node &b,node &c) {
    return l1*(b.y-a.y)*(c.g-b.g)<=l1*(c.y-b.y)*(b.g-a.g);
}
int calc(int i,int p) {
    return a[i].d*a[p].g+a[p].y;
}

void cdq(int l,int r) {
    if(l==r) {
        f[l]=max(f[l],f[l-1]);
        a[l].y=f[l]-a[l].p+a[l].r-a[l].g*a[l].d-a[l].g;
        return;
    }
    int mid=(l+r)/2,k1=l,k2=mid+1;
    rep(i,l,r) {
        if(a[i].id<=mid) tmp[k1++]=a[i];
        else tmp[k2++]=a[i]; 
    }
    rep(i,l,r) a[i]=tmp[i];
    cdq(l,mid);
    int ql=1,qr=1;
    rep(i,l,mid) {
        if(f[a[i].id]<a[i].p) continue;
        while(ql+1<qr&&cmp(a[q[qr-2]],a[q[qr-1]],a[i])) qr--;
        q[qr++]=i;
    } q[qr++]=0;
    rep(i,mid+1,r) {
        while(ql+1<qr&&calc(i,q[ql+1])>calc(i,q[ql])) ql++;
        int p=q[ql];
        f[i]=max(f[i],calc(i,p));
    }
    cdq(mid+1,r);
    sort(a+l,a+r+1,cmpg);
}

signed main() {
    for(int test=1;;test++) {
        n=read(), c=read(), m=read();
        memset(a,0,sizeof(a)), memset(f,0,sizeof(f));
        if(n==0&&m==0&&c==0) break;
        rep(i,1,n) a[i].d=read(), a[i].p=read(), a[i].r=read(), a[i].g=read();
        a[++n]=(node){n,m+1,0,0,0,0};
        sort(a+1,a+n+1,cmpd);
        rep(i,1,n) a[i].id=i;
        f[0]=c;
        cdq(1,n);
        printf("Case %lld: %lld\n",test,f[n]);
    }
    return 0;
}