Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def compl(a, b):
- return a + b in ("AU", "UA", "CG", "GC")
- s = input()
- n = len(s)
- dp = [[0] * n for i in range(n)]
- for i in range(n - 1, -1, -1):
- for j in range(i + 1, n):
- dp[i][j] = dp[i + 1][j - 1] + int(compl(s[i], s[j]))
- for k in range(i, j):
- dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j])
- res = ['.'] * n
- stack = [(0, n - 1)]
- while stack:
- l, r = stack.pop()
- if l >= r:
- continue
- if dp[l][r] == dp[l + 1][r]:
- stack.append((l + 1, r))
- elif dp[l][r] == dp[l][r - 1]:
- stack.append((l, r - 1))
- elif dp[l][r] == dp[l + 1][r - 1] + int(compl(s[l], s[r])):
- res[l] = '('
- res[r] = ')'
- stack.append((l + 1, r - 1))
- else:
- for m in range(l + 1, r):
- if dp[l][r] == dp[l][m] + dp[m + 1][r]:
- stack.append((l, m))
- stack.append((m + 1, r))
- break
- print(''.join(res))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement