fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int dp[6101][6101];
  4. int lcs(string &str,string &pat,int i,int j){
  5.     if(i==str.length()||j==pat.length()){
  6.         return 0;
  7.  
  8.     }
  9.     if(dp[i][j]!=-1)
  10.         return dp[i][j];
  11.     if(str[i]==pat[j]){
  12.         return dp[i][j]=(1+lcs(str,pat,i+1,j+1));
  13.     }
  14.     return dp[i][j]=max(lcs(str,pat,i+1,j),lcs(str,pat,i,j+1));
  15. }
  16. int main(){
  17.     int t;
  18.     cin>>t;
  19.     while(t--){
  20.         string str;
  21.         cin>>str;
  22.         string rev=str;
  23.         reverse(rev.begin(),rev.end());
  24.         //cout<<rev;
  25.         memset(dp,-1,sizeof(dp));
  26.         cout<<(str.length()-lcs(str,rev,0,0))<<endl;
  27.  
  28.     }
  29.  
  30. }
  31.  
Success #stdin #stdout 0.03s 160640KB
comments (?)
stdin
copy 
1
fft
stdout
copy 
1
https://ideone.com/oJYyz3
problem AIBOHP, based on SPOJ submission 23049506 (CPP14), 2019-01-12 14:36:55
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!