0%

【题解】HDU-3842-Machine Works

题目

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]);
}
}