Anupznk

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