Saleh127

UVA 11151 / DP - Edit dis

Nov 25th, 2021 (edited)
101
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-25-18.49.34
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define get_lost_idiot return 0
  9. #define nl '\n'
  10.  
  11. string a;
  12.  
  13. ll dp[1005][1005];
  14.  
  15. ll solve(ll i,ll j)
  16. {
  17.     if(i>j) return 0;
  18.  
  19.     if(i==j) return 1;
  20.  
  21.     if(dp[i][j]!=-1) return dp[i][j];
  22.  
  23.     ll ans=0;
  24.  
  25.     if(a[i]==a[j])
  26.     {
  27.         ans=2+solve(i+1,j-1);
  28.     }
  29.     else
  30.     {
  31.         ans=max(solve(i+1,j),solve(i,j-1));
  32.     }
  33.  
  34.     return dp[i][j]=ans;
  35. }
  36.  
  37. int main()
  38. {
  39.     ios_base::sync_with_stdio(0);
  40.     cin.tie(0);
  41.     cout.tie(0);
  42.  
  43.  
  44.     int tt;
  45.     cin>>tt;
  46.  
  47.     cin.ignore();
  48.     for(int cs=1; cs<=tt; cs++)
  49.     {
  50.         getline(cin,a);
  51.  
  52.         memset(dp,-1,sizeof dp);
  53.  
  54.         cout<<solve(0,a.size()-1)<<nl;
  55.     }
  56.  
  57.  
  58.     get_lost_idiot;
  59. }
  60.  
RAW Paste Data Copied