Advertisement
Saleh127

SPOJ ACODE / DP

Nov 21st, 2021
810
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-21-16.21.18
  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. ll dp[20005],n;
  12. string a;
  13.  
  14. ll solve(ll in)
  15. {
  16.      if(in==n) return 1ll;
  17.      if(a[in]=='0') return 0ll;
  18.      if(dp[in]!=-1) return dp[in];
  19.  
  20.      ll x=0;
  21.  
  22.      x+=solve(in+1);
  23.  
  24.      if(a[in]=='1' || (a[in]=='2' && a[in+1]<'7'))
  25.      {
  26.           x+=solve(in+2);
  27.      }
  28.  
  29.      return dp[in]=x;
  30. }
  31.  
  32. int main()
  33. {
  34.    ios_base::sync_with_stdio(0);
  35.    cin.tie(0);cout.tie(0);
  36.  
  37.  
  38.    while(cin>>a && a!="0")
  39.    {
  40.         memset(dp,-1,sizeof dp);
  41.         n=a.size();
  42.  
  43.         cout<<solve(0)<<nl;
  44.    }
  45.  
  46.  
  47.    get_lost_idiot;
  48. }
  49.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement