|
|
Từ tập các bài có trên SPOJ (oi)
2198. Leaves
Mã bài: NKLEAVES
|
Một ngày thu ðẹp trời, Radu và Mars nhận ra rằng khu vườn của họ chứa ðầy lá rụng. Họ quyết ðịnh gom lá thành ðúng K ðống lá.
Biết rằng khu vườn có dạng một ðường thẳng. 2 người ðã thiết lập một hệ tọa ðộ với gốc ở ðiểm ðầu của khu vườn.
Có N chiếc lá nằm thẳng hàng với trọng lượng khác nhau, khoảng cách giữa 2 chiếc lá liên tiếp là 1. Nghĩa là, chiếc lá ðầu tiên có tọa ðộ 1, chiếc lá
thứ 2 có tọa ðộ 2,..., chiếc lá thứ N có tọa ðộ N. Ban ðầu, 2 người ðang ðứng ở tọa ðộ N.
Radu và Mars thực hiện việc gom lá trong khi rời khỏi khu vườn, do ðó những chiếc lá chỉ có thể di chuyển về bên trái. Chi phí di chuyển một chiếc
lá bằng tích của trọng lượng chếc lá và khoảng cách di chuyển. Hiển nhiên, một trong K ðống lá sẽ nằm ở tọa ðộ 1, tuy nhiên những ðống còn lại có thể
nằm ở bất kỳ vị trí nào.
Yêu cầu: tìm chi phí nhỏ nhất ðể gom N chiếc lá thành ðúng K ðống lá.
Dữ liệu
- Dòng ðầu tiên chứa 2 số nguyên dương N và K, cách nhau bởi 1 khoảng trắng.
- Dòng thứ i trong số N dòng tiếp theo chứa 1 số nguyên dương cho biết trọng lượng của chiếc lá thứ i.
Kết qủa
In ra 1 số nguyên là chi phí nhỏ nhất ðể gom N chiếc lá lại thành ðúng K ðống lá.
Giới hạn
- 0 < N ≤ 100000
- 0 < K ≤ 10, K < N
- Trọng lượng của mỗi chiếc lá không vượt quá 1000.
Ví dụ
Dữ liệu:
5 2
1
2
3
4
5
Kết qủa
13
Giải thích: Cách tốt nhất là ðặt 2 ðống lá ở vị trí 1 và 4.
| Được gửi lên bởi: | Ngô Minh Ðức |
| Ngày: | 2007-12-06 |
| Thời gian chạy: | 1s
|
| Giới hạn mã nguồn: | 50000B |
| Ngôn ngữ cho phép: | Tất cả ngoại trừ: AWK CLOJ ERL F# GO JS PERL 6 PYTH 3.1.2 SCALA SED TCL |
| Nguồn bài: | Campion 2005 |
|
|
|
|
