paradox64ce

delete-and-earn

Aug 15th, 2021
1,125
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     map<int, int> dp , cnt;
  4.     int next(int x){
  5.         auto it = cnt.upper_bound(x);
  6.         if(it==cnt.end()){
  7.             return -1;
  8.         }
  9.         return it->first;
  10.     }
  11.    
  12.     int f(int x){
  13.         if(x==-1){
  14.             return 0;
  15.         }
  16.        
  17.         if(dp.find(x)!=dp.end()){
  18.             return dp[x];
  19.         }
  20.        
  21.         return dp[x] = max(x*cnt[x] + f(next(x+1)), f(next(x)));
  22.     }
  23.    
  24.     int deleteAndEarn(vector<int>& nums) {
  25.         int n = nums.size();
  26.         dp.clear();
  27.         cnt.clear();
  28.         sort(nums.begin(), nums.end());
  29.         int min_e = 1e9;
  30.         // if I am picking a a[i], I should take all of the a[i]'s
  31.         // f(x) = max(x*cnt[x] + f(next(x+1)), f(next(x)))
  32.         // next(x) = next element > x in the map key
  33.        
  34.         for(auto x:nums){
  35.             cnt[x]++;
  36.             min_e = min(min_e, x);
  37.         }
  38.        
  39.         return f(min_e);
  40.     }
  41. };
RAW Paste Data