
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 (64)*(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 a.sa + (ba).sb + (cb).sc + (dc).sd, and our objective is to maximize this sum.
Now, let DP[K1,b] be the optimal placing of (K1) holes when the first is in b (e.g. DP[3,b] = (cb).sc + (dc).sd, for optimal choice of c and d), then DP[K,a] = the minimum of (ba).sb + DP[K1,b], for all possible b.
We can see that (ba).sb + DP[K1,b] form a line equation with gradient sb, and offset b.sb + DP[K1,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 linesweep to find the optimal b for all a in O(n). 