[TJOI2007] 线段

形式化题目

$n \times n$ 的网格上，第 $i$ 行给出一条线段，覆盖列区间 $[L_i, R_i]$ （ $1 \leqslant L_i \leqslant R_i \leqslant n$ ）。

从 $(1,1)$ 出发走到 $(n,n)$ ，只允许三种移动：向下一步（行 $+1$ ，列不变）、向左一步、向右一步，不允许向上。

要求路径在第 $i$ 行把整段 $[L_i, R_i]$ 都走到过。求最小总步数。

因为不能向上走，行只能单调递增，所以「覆盖完第 $i$ 行」必须在离开第 $i$ 行之前完成，每一行恰好被处理一次。这是全题的结构基础。

暴力解法

思路

不做任何结构性假设，直接把「人在哪、这一行走到什么程度」当成状态搜最短路：

状态 $(i, x, m)$ ：在第 $i$ 行第 $x$ 列， $m$ 是 2 位掩码，记录这一行的 $L_i$ 、 $R_i$ 是否已经踩过；
移动左 / 右：行不变，列 $\pm 1$ ，同时点亮新位置的端点（如果它是端点）；
移动向下：只有 $m = 3$ （两端都踩过）时允许，行 $+1$ ，列不变；
起点 $(1, 1, c(1,1))$ ，终点 $(n, n, 3)$ ，BFS 求最短路。

其中 $c(i,x)$ 表示站在 $(i,x)$ 时会点亮哪些端点；当 $L_i = R_i$ 时，一个位置同时点亮两位。

这个做法把所有可能路线都搜过了，显然正确。但状态数是 $n \times n \times 4$ ， $n = 2\times10^4$ 时完全不可行。

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-23 16:38
 * update_at: 2026-10-23 16:38
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// brute.cpp：小数据暴力解，用 BFS 在「网格位置 + 本行已覆盖左右端点」的状态图上搜最短路。
// 不做任何结构性假设（不比 main.cpp 少搜任何一种走法），所以能真正检验 main 的正确性。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 12;  // 暴力只处理小数据：状态数 = n * n * 4，BFS 规模 n^2

int n;
int L[MAXN], R[MAXN];

// dist[row][col][mask]：到达 (row, col) 且第 row 行的覆盖情况为 mask 时的最少步数
// mask 的第 1 位表示左端点 L[row] 已走过，第 2 位表示右端点 R[row] 已走过
int dist[MAXN][MAXN][4];
bool visited[MAXN][MAXN][4];

// 计算站在 (row, col) 时本行的覆盖情况
int mask_at(int row, int col) {
    int mask = 0;
    if (col == L[row]) {
        mask |= 1;
    }
    if (col == R[row]) {
        mask |= 2;
    }
    // 左端点必须被真正“踩过”，L == R 时一个位置同时代表两端
    return mask;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> L[i] >> R[i];
    }

    memset(visited, 0, sizeof(visited));
    memset(dist, 0x3f, sizeof(dist));

    queue<int> q_row, q_col, q_mask;
    // 起点 (1,1)
    int start_mask = mask_at(1, 1);
    dist[1][1][start_mask] = 0;
    visited[1][1][start_mask] = true;
    q_row.push(1);
    q_col.push(1);
    q_mask.push(start_mask);

    int answer = 1 << 30;

    while (!q_row.empty()) {
        int row = q_row.front(); q_row.pop();
        int col = q_col.front(); q_col.pop();
        int mask = q_mask.front(); q_mask.pop();
        int d = dist[row][col][mask];

        // 到达 (n,n) 且最后一行已覆盖完，就是一个合法终点
        if (row == n && col == n && mask == 3) {
            answer = min(answer, d);
        }

        // 三种移动之一：向左
        if (col - 1 >= 1) {
            int ncol = col - 1;
            int nmask = mask | mask_at(row, ncol);
            if (!visited[row][ncol][nmask]) {
                visited[row][ncol][nmask] = true;
                dist[row][ncol][nmask] = d + 1;
                q_row.push(row); q_col.push(ncol); q_mask.push(nmask);
            }
        }

        // 向右
        if (col + 1 <= n) {
            int ncol = col + 1;
            int nmask = mask | mask_at(row, ncol);
            if (!visited[row][ncol][nmask]) {
                visited[row][ncol][nmask] = true;
                dist[row][ncol][nmask] = d + 1;
                q_row.push(row); q_col.push(ncol); q_mask.push(nmask);
            }
        }

        // 向下：只有本行线段走完了才允许
        if (row + 1 <= n && mask == 3) {
            int nrow = row + 1;
            int nmask = mask_at(nrow, col);
            if (!visited[nrow][col][nmask]) {
                visited[nrow][col][nmask] = true;
                dist[nrow][col][nmask] = d + 1;
                q_row.push(nrow); q_col.push(col); q_mask.push(nmask);
            }
        }
    }

    cout << answer << "\n";

    return 0;
}

复杂度

状态数 $O(n^2)$ （行 × 列 × 4 种掩码），每次转移 $O(1)$ ，所以时间与空间都是 $O(n^2)$ 。实现里把数组开到 $n \leqslant 12$ ，只用来对拍。

瓶颈

瓶颈在于：状态里塞了太多「本行已经走到哪」的信息。

$n$ 行 × $n$ 列 × 覆盖掩码，撑起了 $O(n^2)$ 的规模，而真正决定未来的其实只有一个数——这一行结束时人停在哪一列。掩码只是用来判断「能不能往下走」的临时约束，一旦这一行走完就没有意义了。

所以关键问题是：

走完某一行时，人可能停在哪一列？这个集合能不能缩得很小？

正解

关键观察

观察一：行只能单调向下，所以逐行决策。

不能向上走，于是第 $i$ 行被离开后就再也回不去。每一行必须一次走完，处理顺序固定是 $1, 2, \dots, n$ 。问题从「图上的最短路」变成「每行做一个决策的序列」。

观察二：走完一行后，最优解一定停在这行的端点上。

这是整个状态压缩的根基，值得认真证一遍。

先记一个事实。设 $W_{i+1}(c)$ 表示「站在第 $i+1$ 行第 $c$ 列，走完第 $i+1..n$ 行并最终到达 $(n,n)$ 」的最小代价。那么

\bigl\lvert W_{i+1}(c) - W_{i+1}(c')\bigr\rvert \leqslant \lvert c - c'\rvert

理由是：若已经有一条从 $c$ 出发的最优后续路线，从 $c'$ 出发时先在第 $i+1$ 行内横着走 $\lvert c'-c\rvert$ 步到达 $c$ （横走随时允许，不影响后面覆盖整行），再照抄这条路线即可，只多花 $\lvert c'-c\rvert$ 。反过来也成立。即「后续代价」关于入口列是 1-Lipschitz 的。

现在取一条最优路径，看它在第 $i$ 行：进入列是 $c$ ，离开（向下）时停在列 $x$ 。这一行必须覆盖 $[L_i,R_i]$ ，之后再也不会回来，所以在行内必须一次走完。

下面分三种情况，把本行的结束列 $x$ 换成某个端点 $e$ ，并说明总代价不增加。

(1) $x$ 在区间内部（ $L_i < x < R_i$ ）：这一行必须两头都走到，而最后踩到的端点只有一个，设它为 $e$ 。从 $e$ 之后走到 $x$ 的那一段是纯折回，长度 $d = \lvert e - x\rvert > 0$ 。

(2) $x$ 在区间右侧（ $x > R_i$ ）：这一行必须走到 $R_i$ ，之后再往右走出区间直到 $x$ ，尾巴长度 $x - R_i$ 。取 $e = R_i$ ，则 $d = \lvert e - x\rvert = x - R_i$ 。

(3) $x$ 在区间左侧（ $x < L_i$ ）：对称地取 $e = L_i$ ， $d = \lvert e - x\rvert = L_i - x$ 。

三种情况都有同一条尾巴：从「最后一次踩到端点 $e$ 」之后到 $x$ ，长度 $d = \lvert e-x\rvert$ 。删掉这条尾巴、让第 $i$ 行结束在端点 $e$ ，则

第 $i$ 行的代价至少减少 $d$ ；
第 $i+1$ 行的进入列从 $x$ 变成 $e$ ，由 1-Lipschitz 性质，后续代价最多增加 $\lvert e-x\rvert = d$ 。

一减一增互相抵消，总代价不增加，而新的结束列是端点。

这里要小心一个错误说法：「从端点出发去任何地方都不会更远」是假的——端点离区间另一侧的点确实更远（如 $e=6$ 、 $x=4$ 、目标是 $1$ ，则 $\lvert 6-1\rvert > \lvert 4-1\rvert$ ）。真正起作用的是上面两笔账相互抵消：本行省下的 $d$ 步，恰好够支付下一行入口列变化带来的至多 $d$ 步额外代价。

最后一行是唯一的例外：它没有「下一行」来吸收这 $d$ 步，但收尾是从 $x$ 走到 $(n,n)$ ，改成从 $e$ 直接走到 $(n,n)$ ，由三角不等式 $\lvert e-n\rvert \leqslant \lvert e-x\rvert + \lvert x-n\rvert$ 同样不变差。

所以存在一条最优解，使它在每一行结束时都停在该行的端点上。于是「本行覆盖到哪一列」这块内部状态可以整体消掉，每行只保留 2 个状态。

观察三：每行的最优走法只有两种。

从进入列 $c$ 出发覆盖 $[L_i, R_i]$ 并结束在端点，只有两种可能：

走法	结束列	水平代价
先到 $L_i$ ，再一路向右走到 $R_i$	$R_i$	$\lvert c - L_i\rvert + (R_i - L_i)$
先到 $R_i$ ，再一路向左走到 $L_i$	$L_i$	$\lvert c - R_i\rvert + (R_i - L_i)$

而且这两种都是各自的最优：要结束在 $R_i$ ，就一定要碰过 $L_i$ ，所以代价不可能小于 $\lvert c-L_i\rvert + (R_i-L_i)$ ；另一种对称。

思路

定义两个状态（ $1 \leqslant i \leqslant n$ ）：

$f_i$ ：走完第 $1..i$ 行、最后停在第 $i$ 行左端点 $L_i$ 的最短路程；
$g_i$ ：走完第 $1..i$ 行、最后停在第 $i$ 行右端点 $R_i$ 的最短路程。

第 1 行从 $(1,1)$ 出发， $c = 1$ ：

f_1 = \lvert 1 - R_1\rvert + (R_1 - L_1), \qquad g_1 = \lvert 1 - L_1\rvert + (R_1 - L_1)

（停到左端点 $L_1$ ：先走到 $R_1$ 再折回；停到右端点 $R_1$ ：先走到 $L_1$ 再一路向右。）

第 $i \geqslant 2$ 行：先向下走一步（代价 $1$ ），再走本行。上一行可能停在 $L_{i-1}$ 或 $R_{i-1}$ ，取较小的来源：

f_i = \min\Bigl(f_{i-1} + \lvert L_{i-1} - R_i\rvert,\; g_{i-1} + \lvert R_{i-1} - R_i\rvert\Bigr) + (R_i - L_i) + 1

g_i = \min\Bigl(f_{i-1} + \lvert L_{i-1} - L_i\rvert,\; g_{i-1} + \lvert R_{i-1} - L_i\rvert\Bigr) + (R_i - L_i) + 1

注意 $f_i$ （停在 $L_i$ ）的进入列是 $R_i$ ，所以转移里是 $\lvert\cdot - R_i\rvert$ ； $g_i$ 对称。

收尾：从第 $n$ 行的停靠点走到 $(n,n)$ ，只差水平距离：

\text{answer} = \min\Bigl(f_n + \lvert L_n - n\rvert,\; g_n + \lvert R_n - n\rvert\Bigr)

用样例验证一遍（粗体是该行的最优选择）：

行	线段 $[L_i,R_i]$	最优停靠点	$f_i$	$g_i$
1	$[2,6]$	6	9	5
2	$[3,4]$	3	9	10
3	$[1,3]$	1	12	14
4	$[1,2]$	2	15	14
5	$[3,6]$	6	22	19
6	$[4,5]$	4	22	23

（粗体是该行较小的那个状态。）第 6 行更小的是 $f_6 = 22$ ，即停在本行左端点 $4$ ，收尾再从 $4$ 走到 $6$ 。两条路殊途同归： $f_6 + \lvert 4-6\rvert = 22+2 = 24$ ， $g_6 + \lvert 5-6\rvert = 23+1 = 24$ ，答案都是 $24$ 。题面给出的路线在第 6 行走 $6\to 4\to 6$ ，正好对应「停左端点 4、再走到 6」。

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-23 16:38
 * update_at: 2026-10-23 16:38
 */
// main.cpp：线扫一遍，每行只保留「停在线段左端点 / 右端点」两个状态
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 20005;

ll n;
ll L[MAXN], R[MAXN];

// dp_left[i]：走完第 1..i 行的线段，最后停在第 i 行线段的左端点 L[i] 时的最短路程
// dp_right[i]：同上，最后停在第 i 行线段的右端点 R[i]
ll dp_left[MAXN], dp_right[MAXN];

ll abs_dist(ll a, ll b) {
    if (a > b) {
        return a - b;
    }
    return b - a;
}

void read_input() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> L[i] >> R[i];
    }
}

void solve() {
    // 第 1 行从 (1,1) 出发。
    // 想停到 L[1]：先走到 R[1] 再折回 L[1]；想停到 R[1]：直接走到 L[1] 再一路往右。
    ll len1 = R[1] - L[1];
    dp_left[1] = abs_dist(1, R[1]) + len1;
    dp_right[1] = abs_dist(1, L[1]) + len1;

    for (ll i = 2; i <= n; i++) {
        ll len = R[i] - L[i];

        // 上一行无论停在哪，都要先竖直向下走到本行的同一列（代价 1），
        // 然后在本行从这一列出发，覆盖 L[i] 与 R[i]，最后停到目标端点。
        // 停到 L[i]：必须先到 R[i] 再折回，水平代价 = |入口列 - R[i]| + len
        dp_left[i] = min(dp_left[i - 1] + abs_dist(L[i - 1], R[i]),
                         dp_right[i - 1] + abs_dist(R[i - 1], R[i]))
                    + len + 1;

        // 停到 R[i]：必须先到 L[i] 再一路往右，水平代价 = |入口列 - L[i]| + len
        dp_right[i] = min(dp_left[i - 1] + abs_dist(L[i - 1], L[i]),
                          dp_right[i - 1] + abs_dist(R[i - 1], L[i]))
                     + len + 1;
    }

    // 最后还要从第 n 行的停靠点走到 (n,n)，只差水平距离
    ll answer = min(dp_left[n] + abs_dist(L[n], n), dp_right[n] + abs_dist(R[n], n));
    cout << answer << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

复杂度

每行常数次运算，时间 $O(n)$ ，空间 $O(n)$ 。

$n \leqslant 2\times10^4$ ，实测 $n = 2\times10^4$ 时只跑了 7 ms、1 MB 内存。

总结

这题的两步都很典型：

结构观察：不能向上走 ⇒ 行单调 ⇒ 逐行决策，把图搜索变成序列决策。
状态压缩：走完一行后停在区间内部是纯浪费（之后不会回来补），所以最优解必停在端点 ⇒ 每行只剩两个状态。

可以浓缩成一句口诀：

行不能回头，所以逐行做；行内不折返，所以只留两端。

实现上有三个容易写错的细节：

$f_i$ 是「停在左端点」，它的进入列是右端点 $R_i$ ，绝对值里别写反；
每行转移要额外 $+1$ （向下走一步），容易漏；
第 1 行从 $(1,1)$ 出发，也要按同样两种走法初始化；最后还要补上从停靠点到 $(n,n)$ 的水平距离。

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

关键观察

思路

代码

复杂度

总结