fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  5. #define endl "\n"
  6. #define ll long long
  7. #define pb push_back
  8. #define mp make_pair
  9. #define fi first
  10. #define se second
  11.  
  12. int dp[6200][6200]={};
  13. int count(string s,int x,int y)
  14. {
  15.     if(x>=y)
  16.     return 0;
  17.     if(dp[x][y]!=-1)
  18.     return dp[x][y];
  19.     if(s[x]==s[y])
  20.     return dp[x][y]=count(s,x+1,y-1);
  21.  
  22.     else
  23.     return dp[x][y]=min(1+count(s,x,y-1),1+count(s,x+1,y));
  24.  
  25. }
  26. int  main()
  27. {
  28.     IOS;
  29.     int t;
  30.     cin>>t;
  31.      while(t--)
  32.     {
  33.        string s;
  34.        cin>>s;
  35.        memset(dp,-1,sizeof dp);
  36.        int y=count(s,0,s.length()-1);
  37.        cout<<y<<endl;
  38.     }
  39. }
Success #stdin #stdout 0.02s 165376KB
comments (?)
stdin
copy 
1
fft
stdout
copy 
1
https://ideone.com/i5gpmw
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!