0%

[TJOI2007] 线段

题目

题目链接

题目大意:给出 $n$ 条线段的左右端点 $l_i, r_i$,求出从 $(1, 1)$ 走到 $(n, n)$ 且完整经过每条线段需要的最小距离。$1 \le n \le 2 \times 10^4$。

思路

考虑 DP。

这道题的状态还是很好想的,设 $f(i, 1)$ 和 $f(i, 2)$ 分别表示走到第 $i$ 行后停在左右端点需要的最小距离。

初始化 $f(1, 1) = r_i - l_i + r_i - 1, f(1, 2) = r_i - 1$。

转移其实也很好想,如果上一行停在了左端点,那么停在这一行左端点的距离就是这一行的线段长度加上上一行左端点到这一行右端点的距离,停在这一行右端点的距离就是这一行的线段长度加上上一行左端点到这一行左端点的距离。上一行停在右端点的情况同理。

状态转移方程:

草为什么没对齐

最后别忘了是走到 $(n, 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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return;
}

int f[20010][3];
int l[20010], r[20010];
int n;

int main() {
read(n);
for (int i = 1; i <= n; ++i) read(l[i]), read(r[i]);
f[1][1] = r[1] + r[1] - l[1] - 1;
f[1][2] = r[1] - 1;
for (int i = 2; i <= n; ++i) {
f[i][1] = std::min(f[i - 1][1] + abs(r[i] - l[i - 1]), f[i - 1][2] + abs(r[i] - r[i - 1])) + r[i] - l[i] + 1;
f[i][2] = std::min(f[i - 1][1] + abs(l[i] - l[i - 1]), f[i - 1][2] + abs(l[i] - r[i - 1])) + r[i] - l[i] + 1;
}
printf("%d\n", std::min(f[n][1] + n - l[n], f[n][2] + n - r[n]));
return 0;
}