||Let the number of leaves in location i be wi. First, I ignore the first hole since it is always there.
If we do not put any hole, then the total cost = w1 + 2w2 + 3w3 + ... + wn. If we put one hole in position 4, then the total cost will be reduced by 4*(w4 + w5 + w6 + ... + wn). If we put another hole in position 6, then the total cost will be reduced by (6-4)*(w6 + w7 + ... + wn).
Therefore, let si be the sum of wi from i to n, if we put holes in position a,b,c,d then the total reduced cost is
and our objective is to maximize this sum.
Now, let DP[K-1,b] be the optimal placing of (K-1) holes when the first is in b (e.g. DP[3,b] = (c-b).sc + (d-c).sd, for optimal choice of c and d), then DP[K,a] = the minimum of (b-a).sb + DP[K-1,b], for all possible b.
We can see that (b-a).sb + DP[K-1,b] form a line equation with gradient -sb, and offset b.sb + DP[K-1,b].
Hence, to calculate DP[K,a] for all a, first we built the line equation of all b, extract the "promising lines" (gi < gj and oi > oj, where g and o are gradient and offset respectively). Having all the lines, we can do line-sweep to find the optimal b for all a in O(n).