There is N length of signs arranged in a row. The i-th sign has signs[i] length. K workers install signs.

install consists of merging exactly K works, and the work time is of the number of signs to install is equal to the total number of signs in these K.

Find the minimum cost to work time that when all workers finished all sign length.

hint: (Dynamic programming) a sequence of mk1 positions where the work is divided: p_1,p2i satisfies 1p_in. the worker dividing lines, and the meaning is that worker 1 installs signs 1 through p₁, worker 2 installs signs p₁+1 through p₂, and so on up through worker m+1 who installs signs pm through n. Note that dont actually need to use all k workers to get an optimal solution, which is why mk1 rather than m=k1.

input: signs (S) = [3,2,4,1], k= 3

Explanation:

p=<2,3,4>

worker_1 install two signs [3,2] , cost 5 time

worker_2 install one sign [4], cost 4 time

worker_3 install one sign [1], cost 1 time

Question:

1. What is the objective function for this problem? Be precise and mathematical (ideally it should be a single formula).(A function that takes the inputs values (the s_i values and k) and a solution (the p_i) values, and computes how good that solution is.)
2. For an input with n signs and k workers, how many feasible solutions are there?