Saleh127

UVA 10739 / DP - edit dis

Oct 22nd, 2021
899
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-10-23-01.09.17
  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[1002][1002];
  12. string a;
  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=1e6;
  21.  
  22.      if(a[i]==a[j])
  23.      {
  24.           ans=min(ans,solve(i+1,j-1));
  25.      }
  26.      else
  27.      {
  28.           ans=min(ans,1+solve(i+1,j-1)); ///replace i or j th char
  29.           ans=min(ans,1+solve(i+1,j));  ///dlt i th char
  30.           ans=min(ans,1+solve(i,j-1));  ///dlt j th char
  31.      }
  32.  
  33.      return dp[i][j]=ans;
  34. }
  35.  
  36. int main()
  37. {
  38.    ios_base::sync_with_stdio(0);
  39.    cin.tie(0);cout.tie(0);
  40.  
  41.  
  42.    test
  43.    {
  44.         cin>>a;
  45.  
  46.         memset(dp,-1,sizeof dp);
  47.  
  48.         cout<<"Case "<<cs<<": "<<solve(0,a.size()-1)<<endl;
  49.    }
  50.  
  51.  
  52.    get_lost_idiot;
  53. }
  54.  
RAW Paste Data