Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <iostream>
- #include <string>
- #include <algorithm>
- #include <fstream>
- #include <map>
- using namespace std;
- bool is_complementary(char x, char y)
- {
- return (x == 'A' && y == 'U')
- || (x == 'U' && y == 'A')
- || (x == 'C' && y == 'G')
- || (x == 'G' && y == 'C');
- }
- map<pair<int, int>, int> mem;
- int recur(const string& s, int i, int j) {
- if (i >= j)
- return 0;
- auto it = mem.find(make_pair(i, j));
- if (it != mem.end())
- return it->second;
- int a = recur(s, i + 1, j - 1)
- + (is_complementary(s[i], s[j]) && (j - i) - 1 >= 3);
- int b = 0;
- for (int k = i; k < j; k++)
- b = max(b, recur(s, i, k) + recur(s, k + 3, j));
- int c = recur(s, i + 1, j);
- int d = recur(s, i, j - 1);
- int res = max(a, max(b, max(c, d)));
- mem[make_pair(i, j)] = res;
- return res;
- }
- string backtrack(const string& s) {
- string r(s.size(), '.');
- vector<pair<int, int>> st(1, make_pair(0, s.size()));
- while (st.size()) {
- auto p = st.back();
- int i = p.first, j = p.second;
- st.pop_back();
- if (i >= j)
- continue;
- int m = is_complementary(s[i], s[j]) && (j - i) - 1 >= 3;
- if (recur(s, i + 1, j) == recur(s, i, j))
- st.push_back(make_pair(i + 1, j));
- else if (recur(s, i, j - 1) == recur(s, i, j))
- st.push_back(make_pair(i, j - 1));
- else if (recur(s, i + 1, j - 1) + m == recur(s, i, j)) {
- r[i] = '>';
- r[j] = '<';
- st.push_back(make_pair(i + 1, j - 1));
- }
- else {
- for (int k = i + 1; k < j - 1; k++) {
- if (recur(s, i, k) + recur(s, k + 3, j) == recur(s, i, j)) {
- st.push_back(make_pair(k + 3, j));
- st.push_back(make_pair(i, k));
- break;
- }
- }
- }
- }
- return r;
- }
- int main() {
- ifstream fin("input.txt");
- string s;
- getline(fin, s);
- cout << recur(s, 0, s.size()) << ' ' << backtrack(s);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement