一段区间的贡献是这段区间最小的 $h$ 的下标对应的 $b_i$。
分成若干个区间，使得所有区间的贡献和最大。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| int main() {
int N;
cin >> N;
vc<ll> A(N), B(N);
rep(i, N) cin >> A[i];
rep(i, N) cin >> B[i];
vc<ll> dp(N + 1, -lnf);
dp[0] = 0;
rep(i, N) {
int p = i;
rep(j, i, N) {
if (A[p] > A[j]) {
p = j;
}
cmax(dp[j + 1], dp[i] + B[p]);
}
}
cout << dp[N] << "\n";
return 0;
}
|
强行优化这个 $dp$ 的话可以采用单调栈+线段树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| vc<ll> dp(N + 1, -lnf);
rep(i, N * 4) m[i] = -lnf;
upd(0, N, 1, 0, dp[0] = 0);
vector<int> stk{-1};
rep(i, N) {
while (stk.size() > 1 && A[stk.back()] > A[i]) {
add(stk[stk.size() - 2] + 1, stk.back(), 0, N, 1, -B[stk.back()]);
stk.pop_back();
}
add(stk.back() + 1, i, 0, N, 1, B[i]);
stk.emplace_back(i);
dp[i + 1] = m[1];
add(i + 1, i + 1, 0, N, 1, dp[i + 1] + lnf);
}
|
似乎是主流写法。
具有 $O(n)$ 的做法，考虑一个笛卡尔树的树形结构。
考虑你现在做的点是 $x$，且 $x$ 是 $[l, r]$ 内权值最小的下标，他的左儿子 $L$ 是 $[l,x-1]$ 里权值最小的下标，$R$ 同理，这样就建出来了一颗二叉树也就是笛卡尔树，然后 $dp_{x, 0}$ 表示我现在覆盖了 $[l,r]$，得到的最大权值，$dp_{x,1}$ 表示我覆盖了 $l$ 到右端点随意但是小于等于 $r$，得到的最大权值，$dp_{x,2}$ 表示覆盖了左端点随意但是大于等于 $l$ 到 $r$，得到的最大权值，$dp_{x,3}$ 表示覆盖了左大于等于 $l$ 到 右小于等于 $r$，得到的最大权值。这个代码有点发癫。
时间复杂度 $O(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
| #include <bits/stdc++.h>
#ifndef LOCAL
#define debug(...) 42
#else
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#endif
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
vector<int> a(n);
vector<ll> b(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
cin >> b[i];
}
vector<int> stk;
vector<int> l(n, -1);
vector<int> r(n, -1);
for (int i = 0; i < n; i++) {
while (!stk.empty() && a[stk.back()] > a[i]) {
l[i] = stk.back();
stk.pop_back();
}
if (!stk.empty()) {
r[stk.back()] = i;
}
stk.emplace_back(i);
}
int root = stk[0];
auto dfs = [&](auto &self, int u) -> array<ll, 4> {
if (u == -1) {
return array<ll, 4>{0LL, 0LL, 0LL, 0LL};
}
auto L = self(self, l[u]);
auto R = self(self, r[u]);
auto dp = array<ll, 4>{L[1] + b[u] + R[2],
max({L[1], 0LL}) + max({b[u] + R[3], 0LL}),
max({L[3] + b[u], 0LL}) + max({R[2], 0LL}),
max({L[2] + b[u] + R[1], L[2] + b[u], b[u] + R[1],
L[2], R[1], L[3] + b[u] + R[3], L[3] + b[u],
b[u] + R[3], L[3], R[3], b[u], 0LL})};
dp[1] = max(dp[1], dp[0]);
dp[2] = max(dp[2], dp[0]);
dp[3] = max(dp[3], dp[0]);
return dp;
};
cout << dfs(dfs, root)[0] << "\n";
}
|
得知原题之后发现自己在好久之前写过，并且没用这个逆天 dp，但其实下面的这个结构也是笛卡尔树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| i64 solve(const std::vector<int> &b, int l, int r) {
if (l > r)
return 0;
int mid = query(l, r, 0, N - 1, 1).second;
auto lv = solve(b, l, mid - 1);
auto rv = solve(b, mid + 1, r);
auto res = b[mid] + lv + rv;
if (l > 0)
res = std::max(res, rv);
if (r < N - 1)
res = std::max(res, lv);
return res;
}
|
看到 rainboy 的做法又觉得被打击了。
submission
1
2
3
4
5
| for (i = 0; i < n; i++) {
while (cnt && aa[qu[cnt - 1]] > aa[i])
x = max(x, dp[--cnt]);
qu[cnt] = i, dp[cnt] = x, x = dq[cnt] = max(cnt == 0 ? -INF : dq[cnt - 1], x + bb[i]), cnt++;
}
|
$dp_i$ 表示单调栈的第 $i$ 个元素（但是还没有更新到 $qu_i$ 这个位置）的最大值，$dq_i$ 表示单调栈里的第 $i$ 个元素更新到 $qu_i$ 这个位置的最大值，感觉很难想到。
