问题 5342 --线段-训练套题T9T2

5342: 线段-训练套题T9T2

时间限制: 1 Sec  内存限制: 128 MB
提交: 30  解决: 17
[提交][状态][讨论版][命题人:]

题目描述

2. 线段[segement.pas/ c/cpp]

【问题描述】

在一个n*n的平面上,在每一行中有一条线段,第i行的线段的左端点是(i,L(i)),右端点是(i,R(i)),其中1L(i)R(i) n

你从(1,1)点出发,要求沿途走过所有的线段,最终到达(n,n)点,且所走的路程长度要尽量短。

更具体一些说,你在任何时候只能选择向下走一步(行数增加1)、向左走一步(列数减少1)或是向右走一步(列数增加1)。当然,由于你不能向上行走,因此在从任何一行向下走到另一行的时候,你必须保证已经走完本行的那条线段。

【输入数据】

输入文件的第一行有一个整数n,以下n行,在第i行(总第(i+1)行)的两个整数表示Li)和Ri)。

【输出数据】

输出文件仅包含一个整数,你选择的最短路程的长度。

【输入样例】

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

提示

自己画画看,不要想复杂。水水的。

来源

 

[提交][状态]