Question 1. [Usaco2004 Dec] Fence Obstacle Course
给定 \(n\) 个栅栏，第 \(i\) 个栅栏的范围是 \(([L_i,R_i],i)\)，初始 Bessie 位于 \((S,n+1)\) 处，不能从中间跨过栅栏，但是端点处可以，问到达 \((0,0)\) 的横向移动距离最小值。
\(n\leq 5\times 10^4, -10^5\leq L_i < R_i\leq 10^5, -10^5\leq S\leq 10^5\)。
想一下就会发现这不是什么维护类问题，例如维护到达某一行某个特定列坐标的最短距离，考虑 DP。
设 \(f_{i,0/1}\) 表示到达第 \(i\) 个栅栏左/右端点的最小横向移动距离。
然后就可以 \(\mathcal{O}(n^2)\) 转移，而显然一个端点往下走一定是能往下就往下，线段树预处理 \(p_i,q_i\) 表示左右端点不断下落后第一个阻挡的栅栏的编号。
时间复杂度为 \(\mathcal{O}(n\log_2 n)\)。
标签：10,栅栏,2024,leq,端点,mathcal,Oct From： https://www.cnblogs.com/ydzr00000/p/18451372