Saleh127

UVA 11404 / DP - Edit dis

Nov 28th, 2021
687
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-29-01.21.07
  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. pair<ll,string>dp[1005][1005];
  13. string a,y;
  14.  
  15. bool cmp(pair<ll,string>c,pair<ll,string>b)
  16. {
  17.     if(c.first==b.first)
  18.     {
  19.         return c.second<b.second;
  20.     }
  21.     return c.first>b.first;
  22. }
  23.  
  24. pair<ll,string> solve(ll i,ll j)
  25. {
  26.     if(i>j) return {0,""};
  27.  
  28.     if(i==j)
  29.     {
  30.         y=a[i];
  31.         return {1,y};
  32.     }
  33.  
  34.     if(dp[i][j].first!=-1) return dp[i][j];
  35.  
  36.     pair<ll,string>x,y,z;
  37.  
  38.     if(a[i]==a[j])
  39.     {
  40.         x = {2+solve(i+1,j-1).first, a[i]+solve(i+1,j-1).second+a[j]};
  41.     }
  42.     else
  43.     {
  44.          y=solve(i,j-1);
  45.          z=solve(i+1,j);
  46.  
  47.          if(cmp(y,z)) x=y;
  48.          else x=z;
  49.     }
  50.  
  51.     return dp[i][j]=x;
  52. }
  53.  
  54. int main()
  55. {
  56.     ios_base::sync_with_stdio(0);
  57.     cin.tie(0);
  58.     cout.tie(0);
  59.  
  60.  
  61.     while(cin>>a)
  62.     {
  63.         for(ll i=0; i<=a.size(); i++)
  64.         {
  65.             for(ll j=0; j<=a.size(); j++)
  66.             {
  67.                 dp[i][j].first=-1;
  68.             }
  69.         }
  70.  
  71.         cout<<solve(0,a.size()-1).second<<nl;
  72.     }
  73.  
  74.  
  75.     get_lost_idiot;
  76. }
  77.  
RAW Paste Data