Advertisement
Saleh127

UVA 11420 / DP

Nov 9th, 2021
839
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-09-23.00.31
  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 n,s,dp[70][70][2];
  13.  
  14. ll solve(ll in,ll d,ll sec)
  15. {
  16.      if(in==n)
  17.      {
  18.           if(d==s) return 1;
  19.           return 0;
  20.      }
  21.      if(dp[in][d][sec]!=-1) return dp[in][d][sec];
  22.  
  23.      ll ans=solve(in+1,d+sec,1)+solve(in+1,d,0);
  24.  
  25.      return dp[in][d][sec]=ans;
  26. }
  27.  
  28.  
  29. ll solve1(ll in,ll d,ll sec)
  30. {
  31.  
  32.      if(in==0)
  33.      {
  34.           return d==0;
  35.      }
  36.      if(dp[in][d][sec]!=-1) return dp[in][d][sec];
  37.  
  38.      ll ans=0ll;
  39.  
  40.      if(sec==1)
  41.      {
  42.           ans=solve1(in-1,d-1,1)+solve1(in-1,d,0);
  43.      }
  44.      else ans=solve1(in-1,d,1)+solve1(in-1,d,0);
  45.  
  46.      return dp[in][d][sec]=ans;
  47. }
  48.  
  49.  
  50. int main()
  51. {
  52.    ios_base::sync_with_stdio(0);
  53.    cin.tie(0);cout.tie(0);
  54.  
  55.  
  56.    while(cin>>n>>s)
  57.    {
  58.         if(n<0 || s<0) exit(0);
  59.  
  60.         memset(dp,-1,sizeof dp);
  61.  
  62.        //cout<<solve(0,0,1)<<nl; also AC
  63.  
  64.         cout<<solve1(n,s,1)<<nl;
  65.    }
  66.  
  67.  
  68.    get_lost_idiot;
  69. }
  70.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement