二维坐标系中有 $n$ 个矩形，第 $i$ 个矩形在水平方向上覆盖 $[l_i, r_i]$，在竖直方向上覆盖 $[i - 1, i]$，我们要水平移动这些矩形使得它们全部连通，水平移动的花费是移动的距离，求最小费用。
链接
ARC 070E NarrowRectangles
题解
令 $f[i][x]$ 表示前 $i$ 个矩形，第 $i$ 个矩形的左端点为 $x$ 的最小费用，于是我们有一个 $O(nx ^ 2)$ 的暴力转移：
$$f[i][x] = |x - l_i| + \min_{x - (R_{i - 1} - L_{i - 1} \leq x' \leq x + (R_i - L_i))} f[i - 1][x']$$
我们把 $f[i]$ 当作一个函数，对于 $x$ 它返回 $f[i][x]$，其图像是一个由 $2i + 3$ 个部分组成的折线，从左到右的斜率分别为 $-i - 1, -i, \cdots, i, i + 1$，因此这个折线可以用 $l_0, l_1, \cdots, l_i, r_0, r_1, \cdots, r_i, c$ 来表示。
- 对于区间 $(- \infty, l_i]$，斜率为 $i - 1$
- 对于区间 $[l_i, l_{i - 1}]$，斜率为 $i$
- $\cdots$
- 对于区间 $[l_1, l_0]$，斜率为 $-1$
- 对于区间 $[l_0, r_0]$，折线为常数 $c$
- 对于区间 $[r_0, r_1]$，斜率为 $1$
- $\cdots$
- 对于区间 $[r_{i - 1}, r_i]$，斜率为 $i$
- 对于区间 $[l_i, \infty)$，斜率为 $i + 1$
我们用两个 set 来维护即可，时间复杂度 $O(n \log 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
|
#include <bits/stdc++.h>
namespace Task {
const int MAXN = 100000;
#define long long long
std::multiset<long> setL, setR;
int a[MAXN + 1], b[MAXN + 1];
long f[MAXN + 1];
inline void solve() {
std::ios::sync_with_stdio(false), std::cin.tie(NULL), std::cout.tie(NULL);
register int n;
std::cin >> n;
for (register int i = 1; i <= n; i++) std::cin >> a[i] >> b[i];
setL.insert(a[1]), setR.insert(a[1]);
register long tl = 0, tr = 0, ans = 0, nl, nr;
for (register int i = 2; i <= n; i++) {
tl += b[i] - a[i], tr += b[i - 1] - a[i - 1];
nl = *setL.rbegin(), nr = *setR.begin();
if (nl - tl > a[i]) {
ans += std::abs(nl - tl - a[i]), setL.erase(--setL.end());
setL.insert(setL.insert(a[i] + tl), a[i] + tl);
setR.insert(nl - tl - tr);
} else if (a[i] > nr + tr) {
ans += std::abs(nr + tr - a[i]), setR.erase(setR.begin());
setR.insert(setR.insert(a[i] - tr), a[i] - tr);
setL.insert(nr + tr + tl);
} else {
setL.insert(a[i] + tl), setR.insert(a[i] - tr);
}
}
std::cout << ans;
}
#undef long
}
int main() {
Task::solve();
return 0;
}
|
