Advertisement
vinayak7989

Untitled

Oct 3rd, 2022
770
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.41 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int dp[1005][2005], shift = 1e3, cost[1005], tim[1005], n;
  5.  
  6. int go(int i, int more_free_indices) {
  7.       int &ans = dp[i][more_free_indices + shift];
  8.      
  9.       if(ans != -1) return ans;
  10.       if(i == n) {
  11.             if(more_free_indices < 0) return ans = 1e9;
  12.             else return ans = 0;
  13.       }
  14.       ans = 1e9;
  15.       // pay cost
  16.       ans = min(ans, cost[i] + go(i+1, min(n, more_free_indices + tim[i])));
  17.       // take free
  18.       ans = min(ans, go(i+1, more_free_indices - 1));
  19.       return ans;
  20. }
  21.  
  22. int main() {
  23.       memset(dp, -1, sizeof dp);
  24.       cin >> n;
  25.       for(int i = 0; i < n; i++)
  26.             cin >> tim[i] >> cost[i];
  27.      
  28.       // aim: select some indices i1,i2,i3.. tim[i1] + tim[i2] + .. >= n-(count #indices selected) and minimize cost[i1]+cost[i2]..
  29.      
  30.       // when first i indices seen so far.. we could have selected some indices in our ans
  31.       // what matters to the rest of the ans [i+1 .. n] from choices made in [0..i] is just count of indices choosen, sum of time choosen, sum of cost choosen
  32.       // if we think wisely count and sum of time can be taken in one state , [sum] this will tell more_time_available, negative in case we will select indices in future to have enough available time
  33.      
  34.       // So, dp(index, more_time_avail_or more_indices_we_can_choose_for_free) = min cost;
  35.       cout << go(0, 0);
  36. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement