Submit solution
Points:
1.00 (partial)
Time limit:
1.0s
Memory limit:
500M
Author:
Problem type
Allowed languages
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Có (N) hòn đá được đánh số (1,2,3,...,N). Với mỗi (i(1\le i\le N)), chiều cao của hòn đá thứ (i) là (h_i)
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\le N\le 10^5))
- Dòng thứ hai chứa (N) số nguyên : (h1,h2,...,hN) với (1\le hi\le 10^4)
Output
- In ra chi phí tối thiểu cần tìm
Sample
Input #1
4
10 30 40 20
Output #1
30
Input #2
6
30 10 60 10 60 50
Output #2
40
Hint
Ở sample test 1, con ếch sẽ nhảy như sau: (1\rightarrow 2 \rightarrow 4), với chi phí là (|10-30|+|30-20|=30)
Problem source: DP Contest Atcoder
Comments