NKLEAVES - Leaves
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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.
- Người up: paulmcvn
- Nguồn bài: Campion 2005