# Untitled

Oct 3rd, 2022
770
0
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. 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. }