P3842

 每一行走完该行的线段后才能向下一行移动，那么显然可以按行数为阶段进行DP，发现每一行停止的位置不是在左端点就是在右端点，所以设f[i][0\1]表示走完第i行的线段最终停在左/右端点的最短路程， 从该行的左/右端点向下一行的左右端点转移即可，模拟一下可以得到转移方程。 

代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 20010;
 4 int n, l[N], r[N], f[N][2];
 5 int main() {
 6     cin >> n;
 7     for (int i = 1; i <= n; i ++) cin >> l[i] >> r[i];
 8     f[1][0] = r[1] - 1 + r[1] - l[1];
 9     f[1][1] = r[1] - 1;
10     for (int i = 2; i <= n; i ++) {
11         f[i][0] = min(f[i - 1][0] + abs(r[i] - l[i - 1]) + r[i] - l[i] + 1, f[i - 1][1] + abs(r[i - 1] - r[i]) + r[i] - l[i] + 1);
12         f[i][1] = min(f[i - 1][0] + abs(l[i - 1] - l[i]) + r[i] - l[i] + 1, f[i - 1][1] + abs(r[i - 1] - l[i]) + r[i] - l[i] + 1);
13     }
14     printf("%d\n", min(f[n][0] + n - l[n], f[n][1] + n - r[n]));
15     return 0;
16 }