Chú ếch

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, PyPy, Python

Có N hòn đá, được đánh số từ 1 đến N. Với mỗi chỉ số i (1 ≤ i ≤ N), độ cao của hòn đá thứ i là h₁.

Ban đầu, có một chú ếch đang ngồi ở hòn đá thứ nhất và chú sẽ thực hiện các hành động sau:

Nếu chú đang ngồi ở hòn đá i chú có thể nhảy đến hòn đá thứ i + 1 hoặc i + 2. Chú sẽ mất chi phí khi nhảy là |hᵢ - hⱼ| với j là hòn đá mà chú ếch nhảy đến. Bạn hãy giúp chú ếch tìm chi phí tối thiểu để nhảy từ hòn đá thứ nhất đến hòn đá thứ N nhé.

Input

Dòng đầu tiên của dữ liệu vào chứa số nguyên dương N (2 ≤ N ≤ 10⁵), là số lượng hòn đá. Dòng thứ hai gồm N số nguyên hᵢ (1 ≤ i ≤ N, 1 ≤ hᵢ ≤ 10⁴), là độ cao hòn đá thứ i.

Output

Gồm một số nguyên, là chi phí ít nhất để nhảy từ hòn đá thứ nhất đến hòn đá thứ N.

input                                 output
4
10 30 40 20                            30

Giải thích: Một đường đi tối ưu là: 1 → 2 → 4. Chi phí sẽ là |10 - 30| + |30 - 20| = 30.


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.