#P2803. 0x50 动态规划(练习)18:[USACO04DEC]Fence Obstacle Course

0x50 动态规划(练习)18:[USACO04DEC]Fence Obstacle Course

【题意】

给为了让奶牛参与运动,约翰建造了 KK 个栅栏。

每条栅栏可以看做是二维平面上的一条线段,它们都平行于 XX 轴。第 ii 条栅栏所覆盖的 XX 轴坐标的区间为 [Ai,Bi][A_i,B_i]YY 轴高度就是 ii

一开始,奶牛 在坐标 (S,K+1)(S, K + 1) 处,它们的家在原点处,所以要想要回家就必须“跨”一些栅栏。

但奶牛们是跨不过栅栏的,它们只能绕过栅栏。在二维平面上,它们只能沿水平和垂直方向移动, 如果前进的道路上出现栅栏,它们就不能前进,必须沿水平方向移动到没有栅栏的地方再前进。

奶牛们希望走的路越短越好,由于在垂直方向上的路程是确定的,你只需要帮它们求出在水平方向的最短路程就可以了。

【输入格式】

第一行:两个整数 KKSS1K50000,105S1051 \le K \le 50000,−10^5 \le S \le 10^5

第二行到第K+1K+1行:第i+1i+1行有两个整数 AiA_iBiB_i105AiBi105−10^5 \le A_i \le B_i \le 10^5

【输出格式】

单个整数:表示奶牛从起点到终点在水平方向移动的最短总距离

【样例输入】

4 0 
-2 1 
-1 2 
-3 0 
-2 1

【样例输出】

4

【解释】

第四个栅栏是最先遇到的,向右移一格绕过 它。为了绕过第二个栅栏,再向右移一格,最后 为了回到原点向左移两格