Saleh127

Light OJ 1025 / DP - Edit dis

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