Advertisement
Guest User

EBANOE I

a guest
Apr 9th, 2020
435
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.53 KB | None | 0 0
  1. #include <vector>
  2. #include <iostream>
  3. #include <string>
  4. #include <algorithm>
  5. #include <fstream>
  6. #include <map>
  7.  
  8. using namespace std;
  9.  
  10. bool is_complementary(char x, char y)
  11. {
  12.         return (x == 'A' && y == 'U')
  13.                 || (x == 'U' && y == 'A')
  14.                 || (x == 'C' && y == 'G')
  15.                 || (x == 'G' && y == 'C');
  16. }
  17.  
  18. map<pair<int, int>, int> mem;
  19. int recur(const string& s, int i, int j) {
  20.         if (i >= j)
  21.                 return 0;
  22.  
  23.         auto it = mem.find(make_pair(i, j));
  24.         if (it != mem.end())
  25.                 return it->second;
  26.  
  27.         int a = recur(s, i + 1, j - 1)
  28.                 + (is_complementary(s[i], s[j]) && (j - i) - 1 >= 3);
  29.  
  30.         int b = 0;
  31.         for (int k = i; k < j; k++)
  32.                 b = max(b, recur(s, i, k) + recur(s, k + 3, j));
  33.  
  34.         int c = recur(s, i + 1, j);
  35.         int d = recur(s, i, j - 1);
  36.         int res = max(a, max(b, max(c, d)));
  37.  
  38.         mem[make_pair(i, j)] = res;
  39.         return res;
  40. }
  41.  
  42. string backtrack(const string& s) {
  43.         string r(s.size(), '.');
  44.  
  45.         vector<pair<int, int>> st(1, make_pair(0, s.size()));
  46.         while (st.size()) {
  47.                 auto p = st.back();
  48.                 int i = p.first, j = p.second;
  49.  
  50.                 st.pop_back();
  51.                 if (i >= j)
  52.                         continue;
  53.  
  54.                 int m = is_complementary(s[i], s[j]) && (j - i) - 1 >= 3;
  55.                 if (recur(s, i + 1, j) == recur(s, i, j))
  56.                         st.push_back(make_pair(i + 1, j));
  57.                 else if (recur(s, i, j - 1) == recur(s, i, j))
  58.                         st.push_back(make_pair(i, j - 1));
  59.                 else if (recur(s, i + 1, j - 1) + m == recur(s, i, j)) {
  60.                         r[i] = '>';
  61.                         r[j] = '<';
  62.                         st.push_back(make_pair(i + 1, j - 1));
  63.                 }
  64.                 else {
  65.                         for (int k = i + 1; k < j - 1; k++) {
  66.                                 if (recur(s, i, k) + recur(s, k + 3, j) == recur(s, i, j)) {
  67.                                         st.push_back(make_pair(k + 3, j));
  68.                                         st.push_back(make_pair(i, k));
  69.                                         break;
  70.                                 }
  71.                         }
  72.                 }
  73.         }
  74.  
  75.         return r;
  76. }
  77.  
  78. int main() {
  79.         ifstream fin("input.txt");
  80.         string s;
  81.         getline(fin, s);
  82.         cout << recur(s, 0, s.size()) << ' ' << backtrack(s);
  83.         return 0;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement