[UVA][dp] 10874 - Segments＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2013-05-22 10:45:21| 人817| 回0 | 上一篇 | 下一篇

[UVA][dp] 10874 - Segments

推 0 收藏 0 0 站台

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

2 6

3 4

1 3

1 2

3 6

4 5

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);
  &nbs; }
    return 0;
}