P3842 [TJOI2007] 线段
提供的代码使用动态规划来解决这个问题：
数据结构：
a[]数组存储每行线段的左右端点dp[]数组存储到达每行左右端点的最小路径长度
核心函数
sth()：计算从上一行的某个位置到当前行某个位置的路径长度
pan参数决定是从左到右还是从右到左遍历当前行
动态规划转移：
对于每一行，计算从左端点和右端点出发的最短路径
考虑两种遍历方式（从左到右或从右到左）
使用
min()函数选择更优的路径
初始条件和边界处理：
第一行的处理是特殊情况
最后需要从最后一行到达(n,n)
算法优化建议
空间优化：当前代码使用了O(n)的空间，可以进一步优化为只保存前一行的状态。
预处理：可以预先计算某些重复使用的值，减少重复计算。
更清晰的逻辑：可以将路径计算部分拆分为更小的函数，提高代码可读性。
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct {int l, r;
}a[20004], dp[20004];
int n;
ll sum = 0;
ll sth(int i, int k,bool pan) {if (pan == false) {if (k >= a[i].r) {return k - a[i].l + 1;}else if(k<=a[i].l) {return a[i].r - k + (a[i].r - a[i].l) + 1;}else {return (a[i].r - k) + a[i].r - a[i].l + 1;}}else {if (k >= a[i].r) {return (k - a[i].l) + (a[i].r - a[i].l) + 1;}else if (k <= a[i].l) {return a[i].r - k + 1;}else {return ( k- a[i].l) + a[i].r - a[i].l + 1;}}
}
int main(){ios::sync_with_stdio(false); // 禁用同步cin.tie(nullptr); // 解除cin与cout绑定cin >> n;for (int i = 0; i < n; i++) {cin >> a[i].l >> a[i].r;}for (int i = 0; i < n; i++) {if (i == 0){dp[i].l = (a[i].r - 1) + (a[i].r - a[i].l);dp[i].r = a[i].r - 1;}else {dp[i].l = min((sth(i, a[i - 1].l, false) + dp[i - 1].l), (sth(i, a[i - 1].r, false) + dp[i - 1].r));dp[i].r = min((sth(i, a[i - 1].l, true) + dp[i - 1].l), (sth(i, a[i - 1].r, true) + dp[i - 1].r));}}cout << min(n - a[n - 1].l + dp[n - 1].l, n - a[n - 1].r + dp[n - 1].r);return 0;
}