Village and Post Office

Description:

There is a straight highway with villages alongside the highway. The highway is represented as an integer axis, and the position of each village is identified with a single integer coordinate. There are no two villages in the same position. The distance between two positions is the absolute value of the difference of their integer coordinates.

Post offices will be built in some, but not necessarily all of the villages. A village and the post office in it have the same position. For building the post offices, their positions should be chosen so that the average distance from each village to its nearest post office is minimized.

You are to write a program which, given the positions of the villages and the number of post offices, computes the least possible sum of all distances between each village and its nearest post office, and the respective desired positions of the post offices.

Post Office (1160) on POJ

Example:

Note

Idea:

DP

Let the the N villages be at positions 1≤v1≤v2≤…&le:vN We want to place K post offices at K of the N positions v1,…,vN.

Suppose we try to go from left to right, placing post offices and maintain Best[i,r], the best value of placing r post offices among v1,...,vi.

But, if we add a new post office at v{i+1}, the distances for the first i villages may change because the nearest post office for the last few villages in v1,...,vi may now be now be v{i+1} rather than the rightmost post office in v1,...vi.

Can we strengthen the condition for Best[i,r].

Best(i,r) : best way of placing r post offices among v1,...vi such that there is a post office at vi.
How do we calculate Best(i,r)?

Best(i,r) =
             min{
                Best(i-1,r-1) // prev PO at i-1
                Best(i-2,r-1) + Cost(i-1) // Prev PO at i-2
                Best(i-3,r-1) + Cost(i-2,i-1) // Prev PO at i-3
                &hellip:
             }
Thus,

Best(i,r) = min_{1≤j<i-1} Best(j,r-1) + Cost(j+1,…,i-1)
Here Cost(j+1,…,i-1) gives costs for villages v{j+1}…v{i-1} given that nearest neighbouring post offices are at vj and vi.

We have to decide where we place the last post office and compute cost for villages to the right of that. Thus, the final answer is given by the expression:

min_{1≤j≤N} { Best(j,K) + Sum_{j+1<l≤N} distance(vj,vl) }

The complexity is N2K.

Code:

Code