fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define S string
  3. #define nl "\n"
  4. #define speed ios_base::sync_with_stdio(false) , cin.tie(NULL) , cout.tie(NULL);
  5. using namespace std;
  6. vector<pair<int, int> >d={
  7.     {0,-1},{0,1},{1,0},{-1,0}
  8. };
  9. vector<char>dd={'L', 'R' , 'D' , 'U'};
  10. const int MOD = 1e9 + 7;
  11. const int N = 1001;
  12.    int mem[N][N];   bool vis[N][N];
  13.  
  14. int main() {
  15.  
  16.     speed
  17.  
  18.   freopen("input.txt", "r", stdin);
  19.     freopen("output.txt", "w", stdout);
  20.  
  21.  
  22.     S s;
  23.     while (getline(cin, s)) {
  24.         if (s.empty()) {
  25.             break;
  26.         }
  27.         vector<vector<S>>memo(N , vector<S>(N , ""));
  28.          memset(mem , -1 , sizeof(mem));
  29.         memset(vis , 0 , sizeof(vis));
  30.  
  31.         function <int(int , int )> dp =[&](int i , int t)->int {
  32.             if (i > t)return 0;
  33.             int&res=mem[i][t];
  34.             if (~res)return res;
  35.               res = 0;
  36.             if ( i == t ) return  res = 1;
  37.             if ( s[i] == s[t]) {
  38.                 res =  max(res ,dp( i + 1 , t - 1) + 2);
  39.             }
  40.             if (s[i] != s[t]) res = max({res , dp(i + 1 , t)  , dp(i , t - 1)} );
  41.             return res;
  42.         };
  43.  
  44.         function <S(int , int )> bld =[&](int i , int t)->S {
  45.             if ( vis[i][t]) return memo[i][t];
  46.             vis[i][t] = 1 ;
  47.             if (i > t)return "";
  48.  
  49.             int t1 =dp(i + 1 , t)  ,  t2 = dp(i , t - 1), t3 = 0;   if (s[i] == s[t]) t3 =dp( i + 1 , t - 1 ) + 2;
  50.             int a = dp(i , t) ;
  51.             S &ans = memo[i][t];
  52.              ans  = "{" ;
  53.             if ( i == t)    return s.substr( i , 1)   ;
  54.             if ( t3 == a) {
  55.                 ans  = min (ans , s.substr( i , 1) + bld(i + 1 , t - 1 ) + s.substr( i , 1));
  56.             }
  57.  
  58.              if (t2 == a)ans = min ( ans , bld(i , t - 1) );
  59.              if (t1 == a) ans = min ( ans , bld(i + 1 , t ) );
  60.  
  61.             return ans ;
  62.         };
  63.  
  64.  
  65.         dp(0 , s.size()-1 );
  66.         cout<<bld(0 , s.size()-1) << nl;
  67.     }
  68.     return 0;
  69. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cVLu4J
language:
C++ (gcc 8.3)
created:
1 day 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!