Saleh127

UVA 10453 / DP - Edit dis

Nov 29th, 2021
555
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-29-13.30.04
  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. #define nl '\n'
  11.  
  12. ll dp[1005][1005],odd=0;
  13. string a;
  14. vector<ll>x;
  15.  
  16. ll solve1(ll i,ll j)
  17. {
  18.      if(i>=j) return 0;
  19.  
  20.      if(dp[i][j]!=-1) return dp[i][j];
  21.  
  22.      ll ans=0;
  23.  
  24.      if(a[i]==a[j])
  25.      {
  26.           ans=solve1(i+1,j-1);
  27.      }
  28.      else
  29.      {
  30.           ans=1+min(solve1(i+1,j),solve1(i,j-1));
  31.      }
  32.  
  33.      return dp[i][j]=ans;
  34.  
  35. }
  36.  
  37. void solve(ll i,ll j)
  38. {
  39.      if(i>j) return ;
  40.      if(i==j)
  41.      {
  42.           x.push_back(i);
  43.           odd=1;
  44.           return;
  45.      }
  46.      if(a[i]==a[j])
  47.      {
  48.           x.push_back(i);
  49.           solve(i+1,j-1);
  50.           return;
  51.      }
  52.      ll xx,yy;
  53.  
  54.      xx=solve1(i+1,j)+1;
  55.      yy=solve1(i,j-1)+1;
  56.  
  57.      if(xx<yy)
  58.      {
  59.           x.push_back(i);
  60.           solve(i+1,j);
  61.      }
  62.      else
  63.      {
  64.            x.push_back(j);
  65.            solve(i,j-1);
  66.      }
  67. }
  68.  
  69. int main()
  70. {
  71.    ios_base::sync_with_stdio(0);
  72.    cin.tie(0);cout.tie(0);
  73.  
  74.  
  75.    while(cin>>a )
  76.    {
  77.         memset(dp,-1,sizeof dp);
  78.  
  79.         cout<<solve1(0,a.size()-1)<<" ";
  80.  
  81.  
  82.         solve(0,a.size()-1);
  83.  
  84.         for(ll i=0;i<x.size();i++)
  85.         {
  86.              cout<<a[x[i]];
  87.         }
  88.         for(ll i=x.size()-1-odd;i>=0;i--)
  89.         {
  90.              cout<<a[x[i]];
  91.         }
  92.         cout<<nl;
  93.         odd=0;
  94.         x.clear();
  95.    }
  96.  
  97.  
  98.    get_lost_idiot;
  99. }
  100.  
RAW Paste Data