_________________________________________________________________________________

the code should work on the following input and the result should be as the output

_________________________________________________________________________________

input: 3 // number of destinations 1 2 // i = 1, xi=2 2 3 // i = 2, xi=3 3 6 // i = 3, xi=6 2 // k=2 number of stops

output:

2 6 // (for i=1 unhappiness = (2-2)^2 =0, for i=2 unhappiness = (3-2)^2 =1, for i=3 unhappiness = (6-6)^2 =0)

or

3 6 // (for i=1 unhappiness = (2-3)^2 =1, for i=2 unhappiness = (3-3)^2 =0, for i=3 unhappiness = (6-6)^2 =0)

1. Assume there is a bus company serving along a highway with m km and there are n people using this company for travel. They all board the bus at the starting point 0, and each passenger i specifies a destinationx; for the travel before boarding here indicates the distance from the destination to the starting point). If the passenger i leaves the bus at a position y, then the unhappiness of the passenger i will be (x v)?. There are no fixed bus stops. All the stops will be determined after gathering the destinations from all the passingers, and the bus can make at most k stops. ! Devise a dynamic programming algorithm that takes n destinations Xp, ... , Xy and an integer k as input, and outputs an optimal set of positions for k stops that minimizes the sum of the unhappiness of all the passengers. Note that all the inputs given to the algorithm are assumed to be integers and the Xi values are given as sorted in increasing order