Educational DP Contest AtCoder A - Frog 1

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 1G

Problem type

There are N stones, numbered 1,2,,N. For each i (1iN), the height of Stone i is hi.

There is a frog who is initially on Stone 1. He will repeat the following action some number of times to reach Stone N:

  • If the frog is currently on Stone i, jump to Stone i+1 or Stone i+2. Here, a cost of |hihj| is incurred, where j is the stone to land on.

Find the minimum possible total cost incurred before the frog reaches Stone N.

Constraints

  • All values in input are integers.
  • 2N105
  • 1hi104

Input Specification

The first line of input will contain an integer N.

The second line of input will contain N spaced integers, hi, the height of stone i.

Output Specification

Output a single integer, the minimum possible total cost incurred.

Sample Input 1

Copy
4
10 30 40 20

Sample Output 1

Copy
30

Sample Input 2

Copy
2
10 10

Sample Output 2

Copy
0

Sample Input 3

Copy
6
30 10 60 10 60 50

Sample Output 3

Copy
40

Sample Explanations

For the first sample, we can follow path 124, the total cost incurred would be |1030|+|3020|=30.

For the second sample, we can follow the path 12, with the total cost incurred being |1010|=0.

In the last sample, we follow the path 1356, the total cost incurred would be |3060|+|6060|+|6050|=40.


Comments

There are no comments at the moment.