Nội dung Bài tập
- Mã:
- frog2
- Tên:
- Nhảy ếch
- Dạng thi:
- oi
- Thang điểm:
- 10 điểm
- Giới hạn thời gian:
- 2 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- 22120433
Có N hòn đá, được đánh số từ 1 đến N.
Với mỗi hòn đá i, độ cao là hi . Ban đầu, có 1 chú ếch đang ngồi ở hòn
đá thứ nhất và chú sẽ thực hiện liên tục 1 loạt các hành động sau:
· Nếu chú đang ngồi ở hòn đá thứ i , chú có thể
nhảy đến các hòn đá i+1, i+2, … , i+K.
· Chi phí khi nhảy là |hi -hj
| với j là hòn đá sau khi nhảy đến.
Input:
· *Dòng đầu chứa 2 số nguyên dương N và K ( 2
<= N <= 105 ; 1<= K<=100 ), lần lượt lá số hòn đá và giới
hạn nhảy của ếch.
· *Dòng 2 gồm N số nguyên hi (1<= hi
<=104 ), là độ cao hòn đá thứ i.
Output:
Gồm 1 số nguyên là chi phí nhảy từ hòn
đá thứ nhất đến hòn đá thứ N.
Ví dụ:
Input
Output
5 3
10 30 40 50 20
30
Đường đi tối ưu : 1-2-5, chi phí : |10-30|+|30-20|=30
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <iostream>using namespace std;struct ps { int tu, mau; &...