12. (15 points) There are n stations along a coastal railway (n ＞ 0). You're planning to select some of them to open cafes. Three arrays S, L and R have been given, including
ㆍS=(s
1,s
2,..., s
n): the list of the stations froun s
1 (first) to s
n (last).
ㆍL=(l
1,l
2,...，l
n): the locations of the stations, where li is the distance of s
i from the first station s
1. So l
1 = 0 and I
n is the length of the railway.l
1＜l
2＜...＜l
n.
ㆍ R= (r1, r2, ...rn): the revenues of the cafes, where ri (＞ 0) is the revenue for opening a cafe in si.
The only one constraint in your plan is that the distance of any pair of your selected stations should be longer than a given threshold T. If si and sj (i # j) are selected, the total revenue would be li + ly. Different selection leads to different total revenue. Given S, L, R and T, your goal is to pick up a subset of the stations to maximize the total revenue under the constraint. Suppose that f(n) returus the maximum total revenue for the cafes you select from the first n stations. Please answer the following questions. No code is required (code will not be graded).
阿摩線上測驗
登入
-li= 1 (1 ≤i ≤n -1). Give an O(n) solution by defining a recurrence formula for f(n). Clearly explain the meaning of your formula and why it can be computed in O(n) time.