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, \dots, N. For each i (1 \le i \le N), the height of Stone i is h_i.

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 |h_i-h_j| 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.
  • 2 \le N \le 10^5
  • 1 \le h_i \le 10^4

Input Specification

The first line of input will contain an integer N.

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

Output Specification

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

Sample Input 1

4
10 30 40 20

Sample Output 1

30

Sample Input 2

2
10 10

Sample Output 2

0

Sample Input 3

6
30 10 60 10 60 50

Sample Output 3

40

Sample Explanations

For the first sample, we can follow path 1 \to 2 \to 4, the total cost incurred would be |10-30| + |30-20| = 30.

For the second sample, we can follow the path 1 \to 2, with the total cost incurred being |10-10| = 0.

In the last sample, we follow the path 1 \to 3 \to 5 \to 6, the total cost incurred would be |30-60| + |60-60| + |60-50| = 40.


Comments

There are no comments at the moment.