Saleh127

Light OJ 1122 / DP

Oct 20th, 2021 (edited)
112
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-10-20-23.48.58
  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.  
  11. ll dp[15][15];
  12. ll a[20],n,m;
  13.  
  14. ll solve(ll i,ll digit)
  15. {
  16.     if(i==n) return 1ll;
  17.  
  18.     if(dp[i][digit]!=-1) return dp[i][digit];
  19.  
  20.     ll ans=0;
  21.  
  22.  
  23.     for(ll j=0; j<m; j++)
  24.     {
  25.         if(i==0 || abs(digit-a[j])<=2)
  26.         {
  27.             ans+=solve(i+1,a[j]);
  28.         }
  29.     }
  30.  
  31.  
  32.     dp[i][digit]=ans;
  33.  
  34.     return dp[i][digit];
  35. }
  36.  
  37. int main()
  38. {
  39.     ios_base::sync_with_stdio(0);
  40.     cin.tie(0);
  41.     cout.tie(0);
  42.  
  43.     test
  44.     {
  45.  
  46.         cin>>m>>n;
  47.  
  48.         for(ll i=0; i<m; i++) cin>>a[i];
  49.  
  50.         memset(dp,-1,sizeof dp);
  51.  
  52.         cout<<"Case "<<cs<<": "<<solve(0,0)<<endl;
  53.     }
  54.  
  55.  
  56.  
  57.     get_lost_idiot;
  58. }
  59.  
RAW Paste Data Copied