UVa 10874

From Algorithmist
Jump to navigation Jump to search

10874 - Segments[edit]

Summary[edit]

This is a very simple Dynamic Programming problem.

Explanation[edit]

Use the following recurrence relation

Base Case:


Here we came from the ith point in depth d and now we have two choices for going to depth d+1. So, we'll pick the minimum path among them. Cost calculation of each step is a simple math.

Also, need Memoization of size N x 2.

Notes[edit]

  • You need to consider 1 for the down step.

Input[edit]

5
4 4
3 5
1 1
2 3
2 2
9
6 6
2 7
4 8
3 4
5 8
3 5
6 7
1 2
5 6
10
2 8
3 7
5 8
2 6
5 7
6 9
5 10
4 4
7 8
2 7
0

Output[edit]

18
56
66