P5178: 线段-训练套题T9T2
传统题
1.000s
时间限制
128MB
内存限制
3 提交
3 解决
【题目描述】
2. 线段[segement.pas/ c/cpp] 【问题描述】 在一个n*n的平面上，在每一行中有一条线段，第i行的线段的左端点是(i,L(i))，右端点是(i,R(i))，其中1≤L(i)≤R(i) ≤n。 你从(1,1)点出发，要求沿途走过所有的线段，最终到达(n,n)点，且所走的路程长度要尽量短。 更具体一些说，你在任何时候只能选择向下走一步（行数增加1）、向左走一步（列数减少1）或是向右走一步（列数增加1）。当然，由于你不能向上行走，因此在从任何一行向下走到另一行的时候，你必须保证已经走完本行的那条线段。 【输入数据】 输入文件的第一行有一个整数n，以下n行，在第i行（总第（i+1）行）的两个整数表示L（i）和R（i）。 【输出数据】 输出文件仅包含一个整数，你选择的最短路程的长度。 【输入样例】 6 2 6 3 4 1 3 1 2 3 6 4 5 【输出样例】 24 【样例说明】 输入的平面和线段如下图：
我们选择的路线是
(1,1) →(1,6)
→(2,6) →(2,3)
→(3,3) →(3,1)
→(4,1) →(4,2)
→(5,2) →(5,6)
→(6,6) →(6,4) →(6,6)
不难计算得到，路程的总长度是24。
【数据规模】
100%的数据中，n≤20000。
【提示】
自己画画看，不要想复杂。水水的。