题解 P3842 【[TJOI2007]线段】

[更护眼的阅读效果。](https://blog.csdn.net/kkkksc03/article/details/105544432) ## description 在一个 $n\times n$ 矩阵中每一行都有一条线段，找出从 $(1,1)$ 出发不重不漏地遍历每一条线段并走到 $(n,n)$ 结束所需的步数。 ## solution **使用 dp。** 考虑设 $f[i][0/1]$ 表示当前以及遍历完了第 $i$ 行的线段，在左（$0$）/ 右（$1$）端点结束遍历（即准备从这个端点跳到下一行）。 **那么我们可以考虑两行之间衔接的四种情况：** - 左端点到左端点：$f[i][0]=f[i-1][0]+ abs(L[i]-L[i-1])+R[i]-L[i]+1$，其中 $abs(L[i]-L[i-1])$ 为两个左端点之间列数的差距，$R[i]-L[i]$ 为遍历一个线段的步数，而因为向下了一行所以要 $+1$。 - 右端点到左端点：$f[i][0]=f[i-1][1]+ abs(L[i]-R[i-1])+R[i]-L[i]+1$，这个时候同理，只是变换了第 $i-1$ 行的下行节点和转移来的 $f$ 的值。 - 左端点到右端点：$f[i][1]=f[i-1][0]+ abs(R[i]-L[i-1])+R[i]-L[i]+1$。 - 右端点到右端点：$f[i][1]=f[i-1][1]+ abs(R[i]-R[i-1])+R[i]-L[i]+1$。 那么对于 $f[i][0]$ 和 $f[i][1]$ ，我们选择上一行的最优端点转移下来就行了。 **初始化：** 如果刚开始到左端点的话要走两遍线段长，如果右端点可以直接一次性走过去。 **输出：** 由于 $f$ 的值是以线段端点为结束的，而题目要求以 $(n,n)$ 为终点，所以要走到 $n$。 ## code ```cpp #include<cstdio> using namespace std; int f[20005][3];//设f[i][0]表示走完了第i行且走到左端点；设f[i][1]表示走完了第i行且走到了右端点。 int abs(int x) { if(x<0)return -x; return x; } int min(int x,int y) { if(x<y)return x; return y; } int L[20005],R[20005]; int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&L[i],&R[i]); } f[1][0]=L[1]-1+(R[1]-L[1])*2; f[1][1]=R[1]-1; for(int i=2;i<=n;i++) { f[i][0]=min(f[i-1][1]+abs(R[i-1]-R[i]),f[i-1][0]+abs(L[i-1]-R[i]))+R[i]-L[i]+1; f[i][1]=min(f[i-1][1]+abs(R[i-1]-L[i]),f[i-1][0]+abs(L[i]-L[i-1]))+R[i]-L[i]+1; } printf("%d\n",min(f[n][0]+n-L[n],f[n][1]+n-R[n])); return 0; } ```