「CC JUMP」Jump mission-DP + 动态凸包 + 树状数组

有 $N$ 座山排成一排,每座山都有一个 $1 \sim N$ 的唯一编号。第 $i$ 座山的编号为 $P_i$,高度为 $H_i$。
大厨从第一座山出发,目标是到达第 $N$ 座山。他可以从第 $i$ 座山跳到第 $j$ 座山上($i < j, P_i < P_j$),并花费 $(H_i - H_j) ^ 2$ 的能量,当大厨处于第 $i$ 座山时,他还会花费 $A_i$ 的能量($A_i$ 可以为负)。

求最小能量花费。

链接

CC JUMP

题解

首先有一个很显然的 $O(n ^ 2)$ 的 DP。$f[i]$ 表示在第 $i$ 座山上的最小花费,那么

$$f[i] = \min\{f[j] + (h[i] - h[j]) ^ 2\} + a[i]\} \ \ \ \ (j \lt i, P_j \lt P_i)$$

这个式子显然是可以斜率优化的,令 $k = -2h[j], b = f[j] + h[j] ^ 2$,即最小化 $y = kx + b$,其中 $x = h[i]$,那么
$$f[i] = \min\{ kx + b \} + h[i] ^ 2 + a[i]$$

由于有 $P$ 的限制,我们在外层用个树状数组,就变成了单点修改,前缀询问了,里层直接用 std::multiset 维护凸包即可。

时间复杂度 $O(n \log ^ 2 n)$。

代码

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
/**
* Copyright (c) 2016-2018, xehoth
* All rights reserved.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
* http://www.apache.org/licenses/LICENSE-2.0
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*
* 「CC JUMP」Jump mission 29-04-2018
* DP + 动态凸包 + 树状数组
* @author xehoth
*/
#include <bits/stdc++.h>
char pool[1024 * 1024 * 199];
inline void *operator new(size_t size) {
static char *s = pool;
char *t = s;
s += size;
return t;
}
inline void operator delete(void *) {}
inline void operator delete(void *, size_t) {}
struct InputStream {
enum { SIZE = 1024 * 1024 };
char ibuf[SIZE], *s, *t;
inline char read() {
if (s == t) t = (s = ibuf) + fread(ibuf, 1, SIZE, stdin);
return s == t ? -1 : *s++;
}
template <typename T>
inline InputStream &operator>>(T &x) {
static char c;
static bool iosig;
for (c = read(), iosig = false; !isdigit(c); c = read()) {
if (c == -1) return *this;
iosig |= c == '-';
}
for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
if (iosig) x = -x;
return *this;
}
} io;
const long long INF = 0x3f3f3f3f3f3f3f3fll;
struct Point;
bool (*cmp)(const Point &, const Point &);
struct Point {
long long x, y;
mutable double s;
inline bool operator<(const Point &p) const { return cmp(*this, p); }
inline Point operator-(const Point &p) const {
return {x - p.x, y - p.y, 0};
}
inline double operator*(const Point &p) const {
return (double)x * p.y - (double)y * p.x;
}
};
inline bool cmpX(const Point &a, const Point &b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
inline bool cmpS(const Point &a, const Point &b) { return a.s < b.s; }
inline double getSlope(const Point &a, const Point &b) {
return (a.y - b.y) / (double)(b.x - a.x);
}
struct ConvexHull : std::multiset<Point> {
using super = std::multiset<Point>;
bool check(iterator it) {
iterator suc = std::next(it), pre;
if (it == begin())
return suc != end() && it->x == suc->x && it->y <= suc->y;
pre = std::prev(it);
if (suc == end()) return it->x == pre->x && it->y <= pre->y;
return (*pre - *it) * (*it - *suc) >= 0;
}
void insert(const Point &p) {
cmp = cmpX;
iterator it = super::insert(p), suc, pre;
if (check(it)) {
erase(it);
return;
}
for (suc = std::next(it); suc != end() && check(suc);
suc = std::next(it)) {
erase(suc);
}
for (pre = std::prev(it); pre != end() && check(pre);
pre = std::prev(it)) {
erase(pre);
}
if ((suc = std::next(it)) != end()) {
suc->s = getSlope(*it, *suc);
}
if (it != begin()) {
pre = std::prev(it);
it->s = getSlope(*it, *pre);
}
}
long long eval(long long x) const {
if (empty()) return -INF;
cmp = cmpS;
iterator it = --lower_bound({0, 0, (double)x});
return it->x * x + it->y;
}
};
const int MAXN = 300000 + 9;
ConvexHull d[MAXN];
int p[MAXN], n;
long long a[MAXN], h[MAXN], f[MAXN];
inline void insert(int k, long long x, long long y) {
Point pts = {-x, -y, (double)-INF};
for (; k <= n; k += k & -k) {
d[k].insert(pts);
}
}
inline long long query(int k, long long x) {
long long ret = -INF;
for (; k; k ^= k & -k) {
ret = std::max(ret, d[k].eval(x));
}
return ret;
}
int main() {
// freopen("1.in", "r", stdin);
io >> n;
for (int i = 1; i <= n; i++) io >> p[i];
for (int i = 1; i <= n; i++) io >> a[i];
for (int i = 1; i <= n; i++) io >> h[i];
f[1] = a[1];
insert(p[1], -2ll * h[1], f[1] + h[1] * h[1]);
for (int i = 2; i <= n; i++) {
f[i] = -query(p[i], h[i]) + h[i] * h[i] + a[i];
insert(p[i], -2ll * h[i], f[i] + h[i] * h[i]);
}
std::cout << f[n];
return 0;
}
分享到