PreVOI 2023 - Phú Thọ - Truyền tin
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Có ~n~ người đánh số từ ~1~ đến ~n~ xếp thành một hàng và cùng nhau chơi trò chơi truyền tin. Người thứ ~i~ ~(1 \le i \le n)~ có độ trễ khi truyền tin là ~d_i~, khi đó độ trễ người thứ ~i~ truyền tin cho người thứ ~j~ ~(1 \le i \le j \le n)~ được tính bằng ~D(i, j) = \max\{d_i, d_{i+1}, \dots, d_j\}~.
Người quản trò muốn tìm ra ~k~ ~(1 \le k \le n)~ người chơi để tổng độ trễ liên lạc là nhỏ nhất. Một cách hình thức, cần chọn ra ~k~ chỉ số ~1 \le i_1 < i_2 < \dots < i_k \le n~ sao cho ~w = \sum_{1 \le x \le y \le k} D(i_x, i_y)~ là nhỏ nhất.
Yêu cầu: Tính giá trị ~w~ nhỏ nhất.
Input
Dòng đầu chứa hai số nguyên ~n, k~;
Dòng thứ hai chứa ~n~ số nguyên dương ~d_1, d_2, \dots, d_n~ ~(d_i \le 10^9)~.
Output
Ghi ra một số nguyên duy nhất là giá trị ~w~ tính được.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~20\%~ | ~n \le 20~; |
| 2 | ~30\%~ | ~k = 3~ và ~n \le 10^4~; |
| 3 | ~30\%~ | ~n \le 500~; |
| 4 | ~20\%~ | ~n \le 10^4~. |
Sample Input 1
4 3
1 2 2 1
Sample Output 1
10
Notes
Chọn ba người ~1, 2, 4~ có tổng độ trễ nhỏ nhất bằng:
~D(1, 2) + D(1, 4) + D(2, 4) + D(1, 1) + D(2, 2) + D(4, 4) = 10~
Bình luận