divide up the sign so that the maximum workload is as small as possible.

Input: A sequence of sign lengths, s₁,s₂,,s_n, a number of worker k, where kn.

hint: (Dynamic programming) a sequence of mk1 positions where the work is divided: p₁2i 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.

For example:

input S = <2,1,10,77,6>, workers k =3,

one solution: if 1, p₂, p₃>=<2,4,5>, then worker_1 work p₁ = 2 => install s1 and s2 signs, work length 2+1=3; worker_2 work p₂ = 4 => install s3 and s4 signs, work length= 10+77=87; worker_3 work p₃ =5 => install s5, work length= 6 .

when all worker finished the job? is worker_2 finshied 87 length.

another solution: if < p₁, p₂, p₃>=<2,3,5>, then worker_1 work p₁ = 2 => install s1 and s2 signs, work length 2+1=3; worker_2 work p₂ = 3 => install s3 signs, work length= 10, worker_3 work p₃ =5 => install s4,s5, work length=77+ 6=83 .

when all worker finished the job? is worker_3 finshied 83 length.

base on two solutions, the second one (83) is best then first one (87).

Question:

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