P3842 线段

题目描述

在一个 $n \times n$ 的平面上，在每一行中有一条线段，第 $i$ 行的线段的左端点是 $(i, L_{i})$ ，右端点是 $(i, R_{i})$ 。

你从 $(1, 1)$ 点出发，要求沿途走过所有的线段，最终到达 $(n, n)$ 点，且所走的路程长度要尽量短。

更具体一些说，你在任何时候只能选择向下走一步（行数增加 $1$ ）、向左走一步（列数减少 $1$ ）或是向右走一步（列数增加 $1$ ）。当然，由于你不能向上行走，因此在从任何一行向下走到另一行的时候，你必须保证已经走完本行的那条线段。

输入格式

第一行有一个整数 $n$ 。

以下 $n$ 行，在第 $i$ 行（总第 $(i + 1)$ 行）的两个整数表示 $L_{i}$ 和 $R_{i}$ 。

$n \leq 2 \times 10^{4}$ ， $1 \leq L_{i} \leq R_{i} \leq n$ 。

输出格式

仅包含一个整数，你选择的最短路程的长度。

Solution

线性 DP

$f [i] [0]$ 表示走完第 i 行且停在第 i 行的左端点最少用的步数

$f [i] [1]$ 表示走完第 i 行且停在第 i 行的右端点最少用的步数

当走完当前行且停到左端点，那么一定是从右端点过来的

从上一行左端点转移的话就是

$f [i] [0] =$ abs (上一行左端点的坐标 $-$ 本行右端点的坐标)+本行线段长度

从上一行右端点转移的话就是

$f [i] [0] =$ abs (上一行右端点的坐标 $-$ 本行右端点的坐标)+本行线段长度

![|350](/img/user/ZZZ-Misc/Z-Attachment/images-old-ACM/Pasted image 20240314215758.png)

当走完当前行且停到右端点，那么一定是从左端点过来的

从上一行左端点转移的话就是

$f [i] [1] =$ abs (上一行左端点的坐标 $-$ 本行右端点的坐标)+本行线段长度

从上一行右端点转移的话就是

$f [i] [1] =$ abs (上一行右端点的坐标 $-$ 本行右端点的坐标)+本行线段长度

![|350](/img/user/ZZZ-Misc/Z-Attachment/images-old-ACM/Pasted image 20240314220007.png)

注意：到了最后一行走完线段时，还需要达到终点 $(n, n)$ 才算结束。

int f[20010][2];
void solve() {
    int n;cin >> n;vector<int> l(n + 1), r(n + 1);
    for (int i = 1;i <= n;i++)cin >> l[i] >> r[i];
    f[1][0] = r[1] + r[1] - l[1] - 1;
    f[1][1] = r[1] - 1;
    for (int i = 2;i <= n;i++) {
        f[i][0] = min(f[i - 1][0] + abs(l[i - 1] - r[i]),f[i - 1][1] + abs(r[i - 1] - r[i])) + r[i] - l[i] + 1;
        f[i][1] = min(f[i - 1][0] + abs(l[i - 1] - l[i]),f[i - 1][1] + abs(r[i - 1] - l[i])) + r[i] - l[i] + 1;
    }
    cout << min(f[n][0] + n - l[n], f[n][1] + n - r[n]);
}