Highway Billboard Problem | C ++ program to find maximum revenue by placing billboard on the highway with given constraints . ; Array to store maximum revenue at each miles . ; actual minimum distance between 2 billboards . ; check if all billboards are already placed . ; check if we have billboard for that particular mile . If not , copy the previous maximum revenue . ; we do have billboard for this mile . ; If current position is less than or equal to t , then we can have only one billboard . ; Else we may have to remove previously placed billboard ; Driven Program
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxRevenue ( int m , int x [ ] , int revenue [ ] , int n , int t ) { int maxRev [ m + 1 ] ; memset ( maxRev , 0 , sizeof ( maxRev ) ) ; int nxtbb = 0 ; for ( int i = 1 ; i <= m ; i ++ ) { if ( nxtbb < n ) { if ( x [ nxtbb ] != i ) maxRev [ i ] = maxRev [ i - 1 ] ; else { if ( i <= t ) maxRev [ i ] = max ( maxRev [ i - 1 ] , revenue [ nxtbb ] ) ; else maxRev [ i ] = max ( maxRev [ i - t - 1 ] + revenue [ nxtbb ] , maxRev [ i - 1 ] ) ; nxtbb ++ ; } } else maxRev [ i ] = maxRev [ i - 1 ] ; } return maxRev [ m ] ; } int main ( ) { int m = 20 ; int x [ ] = { 6 , 7 , 12 , 13 , 14 } ; int revenue [ ] = { 5 , 6 , 5 , 3 , 1 } ; int n = sizeof ( x ) / sizeof ( x [ 0 ] ) ; int t = 5 ; cout << maxRevenue ( m , x , revenue , n , t ) << endl ; return 0 ; }