[WF 2011]MachineWorks

Description

题解链接

给你 \(n\) 台机器，第 \(i\) 台可以且只能在第 \(d_i\) 天以 \(p_i\) 价值购置。购置后的第二天开始，它每天可以产生 \(g_i\) 的价值。拥有的机器可以卖出，卖出价格为 \(r_i\)，卖出当天不会产生收益，不过卖出当天可以购置新机器。已知每一时刻最多拥有一台机器，初始拥有金钱 \(c\)，并且在第 \(d\) 天后拥有的机器会自动卖出，问这段时间内可以获得的最大利益。多测。

\(1\leq n\leq 10^5\)

Solution

首先按机器出现的时间从小到大排序，之后的讨论默认时间单调不减。

首先一个重要的贪心策略就是，卖出机器当天一定会购入机器。那么记 \(f_i\) 表示购置第 \(i\) 台机器当天产生的最大收益为多少。可以得到转移方程
\[ f_i=\max\{f_j+(d_i-d_j-1)g_j+r_j\}-p_i \]

并且要时刻保证 \(f\) 数组为正值。最后的答案就是 \(\max\limits_{1\leq i\leq n}\{f_i+(d-d_i)g_i+r_i\}\)。

将上述转移方程不考虑 \(p_i\) 变形，得到 \[(d_j+1)g_j-r_j-f_j=d_ig_j-f_i\]

容易发现这一式子可以斜率优化。即用斜率 \(k=d_i\) 的直线在点集 \(\forall j,(g_j, (d_j+1)g_j-r_j-f_j)\) 中做线性规划。由于需要最大化 \(f_i\)，也就是最小化截距，因此维护这一点集的下凸包即可。

由于横坐标 \(g_j\) 不单调，因此用 cdq 分治处理。对左半部分按横坐标排序后，考虑左半部分向右半部分转移。用归并排序代替快排可以在 \(O(n\log n)\) 的时间复杂度内得到解。

Code

#include 
using namespace std;
#define ll __int128
#define x(i) (1ll*a[i].g)
#define y(i) (1ll*(a[i].d+1)*a[i].g-a[i].r-f[i])
const int N = 1e5+5;

int n, c, d, ed[N], q[N], head, tail;
ll f[N];
struct tt {
    int d, p, r, g;
    bool operator < (const tt &b) const {
        return d < b.d;
    }
} a[N];

void cdq(int l, int r) {
    if (l == r) {
        if ((c >= a[l].p ? c-a[l].p : -1) > f[l])
            f[l] = (c >= a[l].p ? c-a[l].p : -1);
        ed[l] = l; return;
    }
    int mid = (l+r)>>1;
    cdq(l, mid);
    head = 0, tail = -1; int flag = 0;
    for (int i = l; i <= mid; i++) {
        if (i != l && x(ed[i]) != x(ed[i-1])) flag = 0;
        if (f[ed[i]] < 0 || flag) continue;
        while (head < tail && 1ll*(y(ed[i])-y(q[tail]))*(x(ed[i])-x(q[tail-1])) <= 1ll*(y(ed[i])-y(q[tail-1]))*(x(ed[i])-x(q[tail]))) --tail;
        q[++tail] = ed[i]; flag = 1;
    }
    for (int i = mid+1; head <= tail && i <= r; i++) {
        while (head < tail && (y(q[head+1])-y(q[head])) <= 1ll*a[i].d*(x(q[head+1])-x(q[head]))) ++head;
        int j = q[head]; if (f[j] < 0) puts("?");
        if (f[j]+1ll*(a[i].d-a[j].d-1)*a[j].g+a[j].r >= a[i].p)
            f[i] = max(f[i], f[j]+1ll*(a[i].d-a[j].d-1)*a[j].g+a[j].r-a[i].p);
    }
    cdq(mid+1, r);
    int i = l, j = mid+1, p = l-1;
    while (i <= mid && j <= r)
        if (x(ed[i]) < x(ed[j]) || (x(ed[i]) == x(ed[j]) && y(ed[i]) < y(ed[j]))) q[++p] = ed[i++];
        else q[++p] = ed[j++];
    while (i <= mid) q[++p] = ed[i++];
    while (j <= r) q[++p] = ed[j++];
    for (int i = l; i <= r; i++) ed[i] = q[i];
}
int main() {
    int t = 0;
    while (true) {
        scanf("%d%d%d", &n, &c, &d);
        if (!(n|c|d)) break;
        for (int i = 1; i <= n; i++)
            scanf("%d%d%d%d", &a[i].d, &a[i].p, &a[i].r, &a[i].g);
        sort(a+1, a+n+1);
        for (int i = 1; i <= n; i++) f[i] = -1;
        cdq(1, n);
        ll ans = c;
        for (int i = 1; i <= n; i++)
            if (f[i] >= 0) ans = max(ans, f[i]+1ll*(d-a[i].d)*a[i].g+a[i].r);
        printf("Case %d: %lld\n", ++t, ans);
    }
    return 0;
}