NKLEAVES - Leaves

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/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:Jimmy
Ngày:2007-12-06
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Campion 2005

hide comments
2016-07-26 17:39:30
sử dụng IT cũng có thể AC zz dù time hơi chậm
2016-07-18 18:15:54 even when you try to hurt me...
https://apps.topcoder.com/forums//?module=Thread&threadID=608334&start=0&mc=12#952198
2016-06-16 11:48:07
Convex hull
2015-12-30 11:02:07 [$Zeus$]
Quy hoạch động bao lồi, tôi code mãi được 30, sửa mãi mới biết spoj khi printf scanf long long phải là %lld chứ ko đc dùng %I64d, ông nào bị thì sửa nhé.
2015-03-05 17:08:55 lucky++
Làm sao có bộ test để thử nhỉ, ức chế quá.
2014-08-13 05:06:34 ■■‡[ND] Bee Sociu■■‡
@@phung van chien :) chem manh qua :) MaxN=100000 kia kia :O O(n*k) thoi
2013-03-28 02:06:26 Trần Vũ Hồng Phúc
bài dễ quá
2012-06-21 11:58:33 phung van chien
bai cua mih thi thuat toan la O(n.(n-1)/2)
2012-06-21 11:57:27 phung van chien
goi L[i,j] la tong chi fi nho nhat de xep n-i+1 la thanh j dong sao cho dong cuoi cung o toa do i tinh tu trai sang(tinh nguoc toa do).ki hieu S[i,k] la tong gia tri de chuyen k-i la tu toa do k den toa do i vao trong toa do i.khi do ta co cong thuc quy hoach dong sau.L[i,j]=min{S[i,k]+L[k+1,j-1])voi k chay tu 1 den n-j-i+1 neu nhu j<n-i+1.con neu j>=n-i+1 thi L[i,j}=0
2010-10-30 14:25:14 Ðỗ Phúc Hảo
Bài này mình không tìm được công thức quy hoạch, ai biết thì giúp em với: phuchaontu@gmail.com
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.