Advertisement
Saleh127

SPOJ SCUBADIV / DP

Nov 7th, 2021
901
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-07-21.49.00
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11.  
  12. ll dp[1005][23][82];
  13.  
  14. ll n;
  15.  
  16. ll ns[1005];
  17. ll os[1005];
  18. ll we[1005];
  19.  
  20. ll solve(ll in,ll ox,ll ni)
  21. {
  22.      if(ox==0 && ni==0) return 0;
  23.  
  24.      if(in>=n) return INT_MAX;
  25.  
  26.      if(dp[in][ox][ni]!=-1) return dp[in][ox][ni];
  27.  
  28.      ll ans=min(solve(in+1,ox,ni),solve(in+1,max(0ll,ox-os[in]),max(0ll,ni-ns[in]))+we[in]);
  29.  
  30.      return dp[in][ox][ni]=ans;
  31. }
  32.  
  33. int main()
  34. {
  35.    ios_base::sync_with_stdio(0);
  36.    cin.tie(0);cout.tie(0);
  37.  
  38.    test
  39.    {
  40.         ll ox,ni;
  41.  
  42.         cin>>ox>>ni>>n;
  43.  
  44.         for(ll i=0;i<n;i++)
  45.         {
  46.              cin>>os[i]>>ns[i]>>we[i];
  47.         }
  48.  
  49.         memset(dp,-1,sizeof dp);
  50.  
  51.         cout<<solve(0,ox,ni)<<nl;
  52.    }
  53.  
  54.    get_lost_idiot;
  55. }
  56.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement