Problem E
Segments
Input: Standard Input

Output: Standard Output

You are tofind the length of the shortest path from the top to the bottom of a gridcovering specified points along the way.

More precisely,you are given an n by n grid, rows 1...n and columns 1…n (1 ≤ n ≤20000). On each row i, two points L(i) and R(i) are given where 1 ≤ L(i)≤ R(i) ≤ n. You are to find the shortest distance from position (1,1), to (n, n) that visits all of the given segments in order. In particular,for each row i, all the points

(i,L(i)); (i, L(i) + 1), (i, L(i) + 2), …, (i, R(i)),

must bevisited. Notice that one step is taken when dropping down between consecutiverows. Note that you can only move left, right and down (you cannot move up alevel). On finishing the segment on row n, you are to go to position (n, n), ifnot already there. The total distance covered is then reported. 

Input

Input file contains maximum 10 sets of inputs.The description of each set is given below:

The first line of each set consists of aninteger n, the number of rows/columns on the grid. On each of the next n lines,there are two integers L(i) followed by R(i) (where 1 ≤ L(i) ≤ R(i)≤ n).

Input is terminated by a set whose value of n is zero. Thisinput should not be processed.

Output

For each setof input output is one integer, which is the length of the (shortest) path from(1, 1) to (n, n) which covers all intervals L(i), R(i).

SampleInput                              Output for Sample Input

6

2 6

3 4

1 3

1 2

3 6

4 5

0

Problem setter: Ian Munro

Special Thanks: Troy Vasiga

/* Sample input description on next page */

Explanation of Sample Input/Output

Below is a pictoral representation of the input.

Notice that on the first row, we must traverse 5 unitsto the right and then drop down one level.

On the second row, we must traverse 3 units to theleft and drop down one level.

On the third row, we must traverse 2 units to the leftand drop down one level.

On the fourth row, we move 1 unit to the right andthen drop down one level.

On the fifth row, we move 4 units to the right anddrop down one level.

On the sixth (and final) row, we move 2 units left,then 2 units right.

In total, we have moved 6 + 4 + 3 + 2 + 5 + 4 = 24units.

題目意思：
從 (1,1) 出發，只能左右或者是往下移動一格，目標達到 (n,n)，而且每個線段都要被走過(整條都要覆蓋在走過的路徑中)，求最少路徑長。

解法：

動態規劃，對於每個狀態保留停留在[左端點]與[右端點]的最小值，
然後進行轉移，從
[左端點]到達[下個左端點]+線段長 會到達 [下一次的右端點]
[左端點]到達[下個右端點]+線段長 會到達 [下一次的左端點]

[右端點]到達[下個左端點]+線段長 會到達 [下一次的右端點]
[右端點]到達[下個右端點]+線段長 會到達 [下一次的左端點]

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int main() {
    int n;
    while(scanf("%d", &n) == 1 && n) {
        int L = 1, R = 1, Li, Ri;
        int dpl = 0, dpr = 0, tdpl, tdpr;
        int i;
        for(i = 0; i < n; i++) {
            scanf("%d %d", &Li, &Ri);
            tdpl = min(dpl+abs(L-Li), dpr+abs(R-Li))+1;
            tdpr = min(dpr+abs(R-Ri), dpl+abs(L-Ri))+1;
            dpr = tdpl + Ri-Li;
            dpl = tdpr + Ri-Li;
            L = Li, R = Ri;
        }
        printf("%d\n", min(dpl+n-Li, dpr+n-Ri)-1);
    }
    return 0;
}

[]