5) There is an s miles long road, with n possible locations for advertisements at distances di,...,dn from the beginning of the road. Putting an advertise- ment at the i'th location brings in revenue p;i. Two advertisements cannot be located closer than distance from each other. Find a set of locations for the advertisement bringing in maximal revenue a) Design a dynamic programming algorithm for this problem. b) Use your algorithm to find the optimal solution for distances 5, 9, 17, 23, revenues 4, 8, 6, 1 and distance 10 Hint: Let rj be the maximal revenue achievable by locations on the first j miles stretch of the road. For every j, let prev(j) be the location preceding dj which is at least distance l from the j'th location. Determine an optimal ity relation for rj involving these quantities and use it to design a dynamic programming algorithm