题面

HDU 3824/ BZOJ 3963 [WF2011]MachineWorks (斜率优化DP+CDQ分治维护凸包)-LMLPHP

BZOJ传送门(中文题面但是权限题)

HDU传送门(英文题面)

分析

定义f[i]f[i]f[i]表示在iii时间(离散化之后)卖出手上的机器的最大收益.转移方程式比较好写f[i]=max{f[j]−p[j]+r[j]+(d[i]−d[j]−1)∗g[j]}f[i]=max\{f[j]-p[j]+r[j]+(d[i]-d[j]-1)*g[j]\}f[i]=max{f[j]−p[j]+r[j]+(d[i]−d[j]−1)∗g[j]}

显然可以斜率优化,移项之后得到(f[j]−p[j]+r[j]−d[j]∗g[j]−g[j])=(−d[i]∗g[j])+(f[i])(f[j]-p[j]+r[j]-d[j]*g[j]-g[j])=(-d[i]*g[j])+(f[i])(f[j]−p[j]+r[j]−d[j]∗g[j]−g[j])=(−d[i]∗g[j])+(f[i])

也就是y=kx+by=kx+by=kx+b的形式,我们要让f[i]f[i]f[i]最大,也就是截距最大.那么维护一个上凸包就行了.为了求凸包插入点的xxx坐标单增,于是用CDQCDQCDQ分治来转移,转移时用归并排序.

啊啊啊啊啊啊啊啊啊啊啊啊啊把whilewhilewhile写成ififif然后WA爆了

CODE

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

template<typename T>inline void read(T &num) {

    char ch; int flg=1;

    while((ch=getchar())<'0'||ch>'9')if(ch=='-')flg=-flg;

    for(num=0;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getchar());

    num*=flg;

}

const int MAXN = 100005;

const double eps = 1e-10;

struct Vector {

    LL x, y;

    Vector(){}

    Vector(LL _x, LL _y):x(_x), y(_y){}

    inline Vector operator -(const Vector &o) { return Vector(x-o.x, y-o.y); }

    inline double operator *(const Vector &o) { return (double)x*o.y - (double)y*o.x; } //会炸longlong,只有用double

}p[MAXN], Q[MAXN];

LL f[MAXN];

struct Node {

    LL p, r, d, g, x, y; int id;

    inline void init() {

        read(d), read(p), read(r), read(g);

        x = g, y = -p+r-d*g-g;

    }

}a[MAXN], tmp[MAXN];

inline bool cmpD(const Node &A, const Node &B) { return A.d < B.d; }

inline bool cmp(const Node &A, const Node &B) {

    return A.x == B.x ? A.y + f[A.id] < B.y + f[B.id] : A.x < B.x;

}

inline int dcmp(double x) {

    return x < -eps ? -1 : x < eps ? 0 : 1;

}

inline LL line(const Vector &P, LL k) { return P.y - k*P.x; } //求截距

void CDQ(int l, int r) {

    if(l == r) { f[l] = max(f[l], f[l-1]); return; }

    int mid = (l + r) >> 1;

    CDQ(l, mid);

    int n = 0, s = 0, t = 0;

    for(int i = l; i <= mid; ++i) if(f[a[i].id] >= a[i].p)

        p[++n] = Vector(a[i].x, a[i].y + f[a[i].id]);

    for(int i = 1; i <= n; ++i) {

        while(s+1 < t && dcmp((Q[t-1]-Q[t-2]) * (p[i]-Q[t-2])) >= 0) --t;

        Q[t++] = p[i];

    }

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

        while(s+1 < t && line(Q[s+1], -a[i].d) >= line(Q[s], -a[i].d)) ++s;

        if(s < t) f[i] = max(f[i], line(Q[s], -a[i].d));

    }

    CDQ(mid+1, r);

    int cur1 = l, cur2 = mid+1;

    for(int i = l; i <= r; ++i) {

        if(cur2 > r || (cur1 <= mid && cmp(a[cur1], a[cur2]))) tmp[i] = a[cur1++];

        else tmp[i] = a[cur2++];

    }

    for(int i = l; i <= r; ++i) a[i] = tmp[i];

}

int n, D, kase;

int main () {

    while(read(n), read(f[0]), read(D), n+f[0]+D) {

        for(int i = 1; i <= n; ++i) a[i].init();

        a[++n].d = D + 1;

        sort(a + 1, a + n + 1, cmpD);

        for(int i = 1; i <= n; ++i) a[i].id = i, f[i] = 0;

        CDQ(1, n);

        printf("Case %d: %lld\n", ++kase, f[n]);

    }

}

//f[i] = f[j] - p[j] + r[j] + (D[i]-D[j]-1)*G[j]

//f[i] + (-D[i])*G[j] = f[j] - p[j] + r[j] - (D[j]+1)*G[j]

KX

HDU 3824/ BZOJ 3963 [WF2011]MachineWorks (斜率优化DP+CDQ分治维护凸包)

题面

分析

CODE