Nộp bài  Các bài nộp  Làm tốt nhất  Về danh sách bài 
NKLEAVES  Leaves 
English  Vietnamese 
One beautiful autumn day Radu and Mars noticed that the garden alley where they usually spend time is rather full of leaves. They decided to gather all the leaves in exactly K piles. The alley is a straight line and they established a coordinate system on the alley, with the origine at the beginning of the alley.
There are N leaves of various weights on the alley, all lined up, and the distance between each consecutive leaves is 1. More precisely the first leaf is at coordinate 1, the second at coordinate 2, ... , the Nth at coordinate N. Initially the two guys are at coordinate N.
The leaf gathering operation takes place as Radu and Mars leave the garden, so the leaves can only be moved to the left. The cost of moving a leaf is equal to its weight times the distance it is moved. Obviously one of the K piles will be at coordinate 1, but the rest can be anywhere.
Task
Find out the total minimum cost of gathering the N leaves in exactly K piles.
Input
The input contains on the first line two positive integers, N and K, separated by a space, having the significance given above. The following N lines contain N positive integers representing the weights of the leaves (line i+1 contains the weight of the leaf located at coordinate i).
Output
The output will contain a single line on which the minimum cost for gathering all the leaves in exactly K piles will be written.
Constraints
 0 < N < 100 001
 0 < K < 11, K < N
 0 < the weight of any leaf < 1 001
Example
Input 5 2 1 2 3 4 5 Output 13
It would be best to form the 2 piles in points 1 and 4. Leaves 1, 2 and 3 are taken to coordinate 1, and 4 and 5 are taken to coordinate 4. The total cost is:
1 * 0 + 2 * 1 + 3 * 2 + 4 * 0 + 5 * 1 = 13
Được gửi lên bởi:  Duc 
Ngày:  20071206 
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 JSRHINO NODEJS PERL6 PYPY RUST SED VB.NET 
Nguồn bài:  Campion 2005 
hide comments


20170804 05:57:05
http://cowboycoder.tech/spoj/spojnkleavesleaves 

20161208 04:41:02 le tuan dung
Tôi là Lê Tuấn Dũng. Xin chào các fan hâm mộ. 

20160730 12:07:36
IT cũng AC đc :) 

20160726 17:39:30
sử dụng IT cũng có thể AC zz dù time hơi chậm 

20160718 18:15:54 even when you try to hurt me...
https://apps.topcoder.com/forums//?module=Thread&threadID=608334&start=0&mc=12#952198 

20160616 11:48:07
Convex hull 

20151230 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é. 

20150305 17:08:55 lucky++
Làm sao có bộ test để thử nhỉ, ức chế quá. 

20140813 05:06:34 ■■‡[ND] Bee Sociu■■‡
@@phung van chien :) chem manh qua :) MaxN=100000 kia kia :O O(n*k) thoi 

20130328 02:06:26 Trần Vũ Hồng Phúc
bài dễ quá 