Saleh127

Light OJ 1033 / DP

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