Chú ếch
Xem dạng PDF
Gửi bài giải
Điểm:
5,00
Giới hạn thời gian:
2.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C++
Có N hòn đá được đánh số 1, 2, 3,.., N. Với mỗi i(1 <= i <= N) chiều cao của hòn đá thứ i là hi Có một con ếch ban đầu ở hòn đá 1. Nó lặp lại hành động sau với một số lần bất kì cho đến khi nó đến được hòn đá N.
- Nếu con ếch đang ở hòn đá i, thì nó có thể nhảy sang hòn đá thứ i + 1 hoặc i + 2 với chi phí là |hi - hj|, trong đó j là vị trí nó muốn nhảy tới.
Tìm chi phí tối thiểu để nó đến được hòn đá thứ N.
INPUT
- Dòng thứ nhất chứa số nguyên N(2 <= N <= 10^5)
- Dòng thứ hai chứa N số nguyên: h1, h2,..., hN với 1 <= hi <= 10^4
OUTPUT
- In ra chi phí tối thiểu cần tìm
SAMPLE INPUT
4
10 30 40 20
SAMPLE OUTPUT
30
Con ếch sẽ nhảy như sau 1 -> 2 -> 4, với chi phí là |10-30| + |30-20| = 30
Bình luận
thiếu đề ạ