Trò chơi (HSG9 VT 2023)

Điểm: 1600 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: GAME.inp

Output: GAME.out

Tác giả:

Sunlight

Dạng bài

Nhân kỷ niệm ngày thành lập Đoàn, cô Tổng phụ trách tổ chức 1 trò chơi có thưởng cho các bạn lớp 9 như sau: Có $N$ ô vuông được vẽ thẳng hàng trên sân trường, các ô vuông được đánh số từ $1, 2, \dots, N$ . Mỗi ô vuông $i$ ( $1\le i\le N$ ) có giá trị năng lượng là $h_i$ . Một bạn học sinh đang ở ô vuông thứ $i$ , bạn ấy có thể nhảy tới ô vuông tiếp theo các cách:

Nếu bạn ở ô vuông thứ $i$ thì bạn có thể nhảy đến ô vuông thứ tự $i+1,i+2,\dots,i+k$
Chi phí năng lượng của bạn tiêu hao cho 1 lần nhảy là $|h_j-h_i|$ với $h_j$ là ô vuông đích mà bạn nhảy tới
Bạn học sinh nào di chuyển từ ô số $1$ đến ô số $N$ với chi phí năng lượng thấp nhất sẽ được cô thưởng một phần quà

Yêu cầu: Hãy tìm chi phí thấp nhất để giúp các bạn học sinh nhảy từ ô vuông số $1$ đến ô vuông thứ $N$

Input và Output

Input: (GAME.inp)

Dòng đầu tiên chứa 2 số $N$ và $K$ cách nhau một ký tự trắng: $N$ là số ô vuông, $K$ là số ô vuông tối đa bạn học sinh có thể nhảy qua ( $2\le N\le 10^5,1\le K\le 100$ )
Dòng thứ hai chứa $N$ giá trị $h_i$ ( $1\le h_i\le 10^4$ ), mỗi số cách nhau một ký tự trắng chỉ phí năng lượng của ô vuông thứ $i$ tương ứng

Output: (GAME.out)

Một số nguyên duy nhất là tổng chi phí phát sinh tối thiểu

Bonus

Bạn có thể giải quyết bài toán này với $N\cdot K\le 10^8,N\le 10^6$ ?

Subtasks

Subtask 1 $(10\%)$ : $N\le 25$ .
Subtask 2 $(30\%)$ : $N\le 10^5,K\le 100$ .
Subtask 3 $(60\%)$ : Không có ràng buộc gì thêm.

Sample

Input (GAME.inp)

5 3
10 25 35 40 20

Output (GAME.out)

Note

Cách nhảy của bạn học sinh sẽ là: $1\rightarrow 2\rightarrow 5$ , tổng chi phí phát sinh sẽ là $|25-10|+|20-25|=20$

Bình luận

Không có bình luận nào.