#P2803. 0x50 动态规划(练习)18:[USACO04DEC]Fence Obstacle Course
0x50 动态规划(练习)18:[USACO04DEC]Fence Obstacle Course
【题意】
给为了让奶牛参与运动,约翰建造了 个栅栏。
每条栅栏可以看做是二维平面上的一条线段,它们都平行于 轴。第 条栅栏所覆盖的 轴坐标的区间为 , 轴高度就是 。
一开始,奶牛 在坐标 处,它们的家在原点处,所以要想要回家就必须“跨”一些栅栏。
但奶牛们是跨不过栅栏的,它们只能绕过栅栏。在二维平面上,它们只能沿水平和垂直方向移动, 如果前进的道路上出现栅栏,它们就不能前进,必须沿水平方向移动到没有栅栏的地方再前进。
奶牛们希望走的路越短越好,由于在垂直方向上的路程是确定的,你只需要帮它们求出在水平方向的最短路程就可以了。
【输入格式】
第一行:两个整数 和 ,
第二行到第行:第行有两个整数 和 ,
【输出格式】
单个整数:表示奶牛从起点到终点在水平方向移动的最短总距离
【样例输入】
4 0
-2 1
-1 2
-3 0
-2 1
【样例输出】
4
【解释】
第四个栅栏是最先遇到的,向右移一格绕过 它。为了绕过第二个栅栏,再向右移一格,最后 为了回到原点向左移两格