【题解】HDU-3842-Machine Works

Posted on Edited on In Disqus:

题目

http://acm.hdu.edu.cn/showproblem.php?pid=3842

WF 2011 数据

题意

\(D​\) 天，初始资金 \(C​\)，\(n​\) 台机器，最多持有一台机器。每台仅能够在 \(D_i​\) 天购买，价格 \(P_i​\)，可以在之后任意一天以 \(R_i​\) 卖出，从购入次日起每天产生 \(G_i​\) 的收益，卖出当天无法获得收益，但是可以立刻购入另一台机器。在 \(D+1​\) 天卖出手中机器并结账。

题解

先将所有机器按照 \(D_i\) 排序，然后 DP。设 \(f_i\) 为在 \(D_i\) 天卖出机器的最大收益。 \[ f_i=\max \{ f_{i-1}, f_j - P_j + R_j + (D_i - D_j - 1) \times G_j \;|\; \forall f_j > P_j\} \\ x=G_j,k=D_i,y=f_j-P_j+R_j-(D_j+1) \cdot G_j \\ kx+y=F\\ -kx+F=y \]

\(x\) 不单调，\(k\) 单调，使用 cdq 分治维护上凸壳。

由于只按 \(x\) 没按 \(y\) 对点进行排序，导致 WA 了很久。\(y\) 可以按升序，也能按降序，都能 AC。因为对于最开始的若干个横坐标相同的点，只会保留最后一个和第一个，而需要的是 \(y\) 最大的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args<< " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int maxn = 1E5 + 100;
struct Q {
    LL D, P, R, G;
};
struct P {
    LL x, y;
};
P operator - (P& a, P& b) { return {a.x - b.x, a.y - b.y}; }
Q a[maxn];
LL n, m, C;
LL f[maxn];

__int128 det(P a, P b) {
    return (__int128)a.x * b.y - (__int128)a.y * b.x;
}

void go(LL l, LL r) {
    if (l + 1 == r) return;
    LL m = l + r >> 1;
    go(l, m);
    static deque<P> p, q; p.clear(); q.clear();
    FOR (i, l, m)
        if (f[i] >= a[i].P)
            p.push_back({a[i].G, f[i] - a[i].P + a[i].R - (a[i].D + 1) * a[i].G});
    if (p.empty()) { go(m, r); return; }
    sort(p.begin(), p.end(), [](const P& a, const P& b){
        if (a.x == b.x) return a.y > b.y;
        return a.x < b.x;
    });
    for (P& x: p) {
        LL t;
        while ((t = q.size()) >= 2 && det(q[t - 1] - q[t - 2], x - q[t - 1]) >= 0)
            q.pop_back();
        q.push_back(x);
    }
    FOR (i, m, r) {
        auto ans = [&](LL k) { return q[k].y + q[k].x * a[i].D; };
        while (q.size() >= 2 && ans(0) <= ans(1)) q.pop_front();
        f[i] = max(f[i], ans(0));
    }
    go(m, r);
}

int main() {
    int Ca = 0;
    while (cin >> n >> C >> m) {
        if (!(n || C || m)) break;
        FOR (i, 0, n) scanf("%lld%lld%lld%lld", &a[i].D, &a[i].P, &a[i].R, &a[i].G);
        a[n++] = {m + 1, 0, 0, 0};
        sort(a, a + n, [](const Q &a, const Q &b) { return a.D < b.D; });
        FOR (i, 0, n) f[i] = C;
        go(0, n);
        printf("Case %d: %lld\n", ++Ca, f[n - 1]);
    }
}