Advertisement
kostes

popel

Jan 7th, 2019
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.11 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define f first
  4. #define s second
  5. #define all(c) c.begin(),c.end()
  6. using namespace std;
  7. typedef long long ll;
  8. const ll INF64 = 1e18 + 1337;
  9. const int INF32 = 1e9 + 228;
  10. const int MOD = 1e9 + 7;
  11. int main()
  12. {
  13. ios_base::sync_with_stdio(0);
  14. #ifndef __WIN32
  15. ifstream cin("input.txt");
  16. ofstream cout("output.txt");
  17. #endif
  18. cin.tie(0);cout.tie(0);
  19.  
  20. int buf;
  21. cin >> buf;
  22. string s;
  23. cin >> s;
  24. int n = s.length();
  25. vector< vector<string> > dp(n, vector<string>(n, ""));
  26. for(int i = 0; i < n; i++) dp[i][i].pb(s[i]);
  27. for(int r = 0; r < n; r++)
  28. {
  29. for(int l = r - 1; l >= 0; l--)
  30. {
  31. if(s[l] == s[r])
  32. dp[l][r] = s[l] + dp[l + 1][r - 1] + s[r];
  33. else
  34. {
  35. if(dp[l][r - 1].length() > dp[l + 1][r].length())
  36. dp[l][r] = dp[l][r - 1];
  37. else dp[l][r] = dp[l + 1][r];
  38. }
  39. }
  40. }
  41. cout << dp[0][n - 1];
  42.  
  43. #ifndef __WIN32
  44. cin.close();
  45. cout.close();
  46. #endif
  47. return 0;
  48. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement