Difficult Algorithm!

[razzle]

Your problem eludes a dynamic programming formulation (at least I couldn't do it).

Well, I think I can now.

The villages are visited in order along the street (from lower distances to higher).

The first and the last hospitals are special cases. We start with the first hospital and it can be placed at any village. Then for each placed hospital we place the next at a higher distance. When calculating the total distances we include villages at lover distances only, except for the last hospital when all villages are included.

The hospitals are placed in stages, one in each stage. In each stage we calculate the lowest total distance for each possible placement of one hospital by considering the previous stage only. When a hospital is placed it adds to the total distance function but the addition is independent of placements made in earlier stages. At each stage we have the best possible placements so far and we can track back which placements led up to them. This is also true for the final stage where the best placement of the last hospital will reveal the best placement of all hospitals, and we have an optimal solution.

That's a proper dynamic programming formulation but it's just a sketch of course. The rest is the homework.