# mobile tower

Jul 22nd, 2021
940
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include<bits/stdc++.h>
2. using namespace std;
3.
4. void printSolution(vector <int> bestPlacesIndex, int sites[]){
5.     cout << "Best sites to place the towers" << endl;
6.     for (int i = 0; i<bestPlacesIndex.size(); i++) {
7.         cout << sites[bestPlacesIndex[i]] << " ";
8.     }
9. }
10.
11. void printSol(int solution[], int n){
12.     for (int i = 0; i<n; i++){
13.         cout<< solution[i] << " ";
14.     }
15.     cout<< endl;
16. }
17.
18. int maxRevenue(int m, int sites[], int cost[], int n, int t){
19.     int solution[m+1];
20.     vector <int> bestPlacesIndex;
21.     memset(solution, 0, sizeof(solution));
22.
23.     int nextTower = 0;
24.
25.     for(int i = 1; i <= m; i++){
26.         if(nextTower > n){ // meaning all the available towers are done
27.             solution[i] = solution[i-1];    // now all we can do is copy the cost for the rest of the miles,
28.                                            // there is no option to change the cost since we are out of towers
29.         } else{
30.             if(sites[nextTower] != i) {
31.                 solution[i] = solution[i-1]; // just copying the previous cost since we do not have any tower available for i-th mile
32.             } else{ // we have a tower available for this position
33.                 if(i <= 2*t){  // we are less than or equal to 2t distance from the starting position
34.                               // meaning we need to place only 1 tower
35.
36.                     if(solution[i-1] < cost[nextTower] && solution[i-1] > 0){
37.                         solution[i] = solution[i-1];
38.                     } else{
39.                         solution[i] = cost[nextTower];
40.
41.                     }
42.
43.
44.                 } else { // we have two options now
45.                     // 1. take the next tower and add revenue
46.                     // 2. do not take the next tower
47. //                    solution[i] = min(solution[i-2*t-1] + cost[nextTower],
48. //                                                  solution[i-1]);
49.
50.
51.                     if(solution[i-2*t-1] + cost[nextTower] > solution[i-1] && solution[i-1] > 0) {
52.                         solution[i] = solution[i-1];
53.
54.                     } else{
55.                         solution[i] = solution[i-2*t-1] + cost[nextTower];
56.                     }
57.                 }
58.                 printSol(solution, m+1);
59.                 nextTower++;
60.             }
61.         }
62.     }
63.
64.     return solution[m];
65. }
66.
67. int main(){
68.
69.     int miles = 10;
70.     int sites[] = {2, 4,  6, 7, 8, 9, 10};
71.     int cost[] = {4, 3, 5, 6, 5, 3, 2};
72.     int n = sizeof(sites)/sizeof(sites[0]);
73.     int t = 2;
74.     cout <<endl<< maxRevenue(miles, sites, cost, n, t) << endl;
75. }
76.
RAW Paste Data