Frog 1
Xem dạng PDF
Gửi bài giải
Điểm:
14,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho n viên đá, viên đá thứ i có độ cao là ~h_i~. Con ếch đang đứng tại viên đá thứ nhất. Tại vị trí thứ i con ếch có thể nhảy sang hòn đá thứ i + 1 hoặc hòn đá thứ i + 2 với chi phí nhảy là |~h_i - h_j~| với j là vị trí đáp của chú ếch.
Yêu cầu: Hãy tìm chi phí ngắn nhất để chú ếch tới được hòn đá thứ n.
Input
- Dòng đầu gồm n là số lượng hòn đá ~(1 \le n \le 10^5)~
- Dòng sau gồm n số, số thứ i thể hiện hi là chiều cao của viên đá thứ i ~(1 \le h_i \le 10^4)~
Output
- Gồm một dòng duy nhất là đáp án cần tìm
Examples
Input
4
10 30 40 20
Output
30
Input
2
10 10
Output
0
Bình luận
dp[i] = min(dp[i - 1] + abs(a[i] - a[i - 1]), dp[i - 2] + abs(a[i] - a[i - 2]));