You have a highway of length M miles and n possible billboard sites at positions x1 < x2 < ... < xn (each in [0, M]). Placing a billboard at position xi yields revenue ri. Two billboards must be strictly more than k miles apart (the original statement uses k = 5). Choose a subset of sites to maximize total revenue.
Input: x =[6, 7, 12, 13, 14], revenue =[5, 6, 5, 3, 1], distance = 20, milesRestriction = 5;
Output: 10
Explanation: Choose billboards at positions `6` (revenue 5) and `12` (revenue 5). These two positions are 6 miles apart which satisfies the `milesRestriction = 5` (they must be strictly more than 5 miles apart). Any other selection that tries to include position `7` would conflict with `6` (distance 1) and provides less or equal revenue. Total revenue = 5 + 5 = 10.
If you know the maximum revenue MR(i-1) up to mile i-1, then for mile i either there is no billboard placed at i (so MR(i) = MR(i-1)), or there is a billboard at i with revenue r and you must add that to MR(i - (k+1)) (the last mile that is safely more than k miles before i). Iterate miles from 0..M.
classSolution {
publiclongmaxRevenueByMiles(int M, int[] x, int[] r, int k) {
long[] mr =newlong[M+1];
int idx = 0, n = x.length;
for (int i = 1; i <= M; ++i) {
mr[i]= mr[i-1];
if (idx < n && x[idx]== i) {
long take = r[idx]+ (i - (k+1) >= 0 ? mr[i-(k+1)] : 0);
mr[i]= Math.max(mr[i], take);
++idx;
}
}
return mr[M];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from typing import List
classSolution:
defmax_revenue_by_miles(self, M: int, x: List[int], r: List[int], k: int) -> int:
mr = [0] * (M +1)
idx =0 n = len(x)
for i in range(1, M +1):
mr[i] = mr[i-1]
if idx < n and x[idx] == i:
take = r[idx]
if i - (k +1) >=0:
take += mr[i - (k +1)]
mr[i] = max(mr[i], take)
idx +=1return mr[M]
Treat each billboard as an interval at point xi with profit ri. For billboard i we need the last billboard j < i with x[j] <= x[i] - (k+1). Let p(i) be that index (or 0 if none). Then dp[i] = max(dp[i-1], r[i] + dp[p(i)]) — the standard weighted-interval DP.
classSolution {
public:longlong maxRevenueByIndex(const vector<int>& x, const vector<int>& r, int k) {
int n = x.size();
vector<longlong> dp(n+1, 0);
for (int i =1; i <= n; ++i) {
int need = x[i-1] - (k+1);
int lo =0, hi = i-2, p =0;
while (lo <= hi) {
int mid = (lo+hi)/2;
if (x[mid] <= need) { p = mid+1; lo = mid+1; } else hi = mid-1;
}
dp[i] = max(dp[i-1], r[i-1] + dp[p]);
}
return dp[n];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
packagemainimport"sort"funcmaxRevenueByIndex(x []int, r []int, kint) int {
n:= len(x)
dp:= make([]int, n+1)
fori:=1; i<=n; i++ {
need:=x[i-1] - (k+1)
// find rightmost index with x[j] <= needj:=sort.SearchInts(x, need+1) // returns first > needdp[i] = dp[i-1]
val:=r[i-1]
ifj>=0 { val+=dp[j] }
ifval > dp[i] { dp[i] = val }
}
returndp[n]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.*;
classSolution {
publiclongmaxRevenueByIndex(int[] x, int[] r, int k) {
int n = x.length;
long[] dp =newlong[n+1];
for (int i = 1; i <= n; ++i) {
int need = x[i-1]- (k+1);
int j = Arrays.binarySearch(x, 0, i-1, need + 1);
if (j < 0) j =-j - 1; // first >= need+1long take = r[i-1]+ dp[j];
dp[i]= Math.max(dp[i-1], take);
}
return dp[n];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
from typing import List
import bisect
classSolution:
defmax_revenue_by_index(self, x: List[int], r: List[int], k: int) -> int:
n = len(x)
dp = [0] * (n +1)
for i in range(1, n+1):
need = x[i-1] - (k +1)
j = bisect.bisect_right(x, need) # first index > need take = r[i-1] + dp[j]
dp[i] = max(dp[i-1], take)
return dp[n]