Atcoder Educational DP Contest - Problem A: Frog 1

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
_minhduc
Dạng bài
Điểm: 1000 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Có \(N\) hòn đá được đánh số từ \(1,2,\ldots,N\). Hòn đá thứ \(i\) có chiều cao là \(h_i\).

Ban đầu, có một con ếch đang ngồi ở hòn đá thứ nhất. Con ếch sẽ lặp đi lặp lại thao tác sau nhiều lần để đến được hòn đá thứ \(N\):

  • Nếu con ếch đang ở hòn đá thứ \(i\), nó có thể nhảy đến hòn đá thứ \(i+1\) hoặc hòn đá thứ \(i+2\) với chi phí là \(|h_i-h_j|\) (\(j\) là hòn đá mà con ếch nhảy đến).

Bạn hãy giúp con ếch tìm chi phí tối thiểu để nhảy từ hòn đá thứ nhất tới hòn đá thứ \(N\) nhé.

Input

  • Dòng thứ nhất chứa một số nguyên dương \(N\) (\(2 \le N \le 10^5\)).
  • Dòng thứ hai chứa \(N\) số nguyên \(h_1,h_2,\ldots,h_N\) (\(1 \leq h_i \leq 10^4\)).

Output

  • Một dòng chứa một số nguyên duy nhất là kết quả bài toán.

Example

Test 1
Input 
4
10 30 40 20
Output 
30
Note

Con ếch nhảy theo lộ trình \(1 -> 2 -> 4\). Chi phí là \(|10 - 30| + |30 - 20| = 30\).

Test 2
Input 
2
10 10
Output 
0
Note

Con ếch nhảy theo lộ trình \(1 -> 2\). Chi phí là \(|10 - 10| = 0\).

Bình luận