Advertisement
Josif_tepe

Untitled

Apr 6th, 2023
509
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.93 KB | None | 0 0
  1. #include <iostream>
  2. #include <map>
  3. #include <cstring>
  4. using namespace std;
  5. string s;
  6. int n;
  7. map<pair<char, char>, bool> mapping;
  8. int dp[222][222];
  9. int rec(int i, int j) {
  10.     if(j - i <= 1) {
  11.         return 0;
  12.     }
  13.     if(dp[i][j] != -1) {
  14.         return dp[i][j];
  15.     }
  16.     int result = 0;
  17.     if(mapping[make_pair(s[i], s[j])]) {
  18.         result = max(result, rec(i + 1, j - 1) + 1);
  19.     }
  20.     for(int k = i; k < j; k++) {
  21.         result = max(result, rec(i, k) + rec(k + 1, j));
  22.     }
  23.     return dp[i][j] = result;
  24. }
  25. int main() {
  26.     ios_base::sync_with_stdio(false);
  27.     cin >> n >> s;
  28.     mapping[make_pair('A', 'U')] = true;
  29.     mapping[make_pair('U', 'A')] = true;
  30.     mapping[make_pair('C', 'G')] = true;
  31.     mapping[make_pair('G', 'C')] = true;
  32.     mapping[make_pair('G', 'U')] = true;
  33.     mapping[make_pair('U', 'G')] = true;
  34.     memset(dp, -1, sizeof dp);
  35.     cout << rec(0, n - 1) << endl;
  36.      return 0;
  37. }
  38.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement