Advertisement
petrtsv

Untitled

Dec 10th, 2019
177
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.97 KB | None | 0 0
  1. def compl(a, b):
  2. return a + b in ("AU", "UA", "CG", "GC")
  3.  
  4.  
  5. s = input()
  6. n = len(s)
  7.  
  8. dp = [[0] * n for i in range(n)]
  9.  
  10. for i in range(n - 1, -1, -1):
  11. for j in range(i + 1, n):
  12. dp[i][j] = dp[i + 1][j - 1] + int(compl(s[i], s[j]))
  13.  
  14. for k in range(i, j):
  15. dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j])
  16.  
  17. res = ['.'] * n
  18.  
  19. stack = [(0, n - 1)]
  20. while stack:
  21. l, r = stack.pop()
  22.  
  23. if l >= r:
  24. continue
  25.  
  26. if dp[l][r] == dp[l + 1][r]:
  27. stack.append((l + 1, r))
  28. elif dp[l][r] == dp[l][r - 1]:
  29. stack.append((l, r - 1))
  30. elif dp[l][r] == dp[l + 1][r - 1] + int(compl(s[l], s[r])):
  31. res[l] = '('
  32. res[r] = ')'
  33. stack.append((l + 1, r - 1))
  34. else:
  35. for m in range(l + 1, r):
  36. if dp[l][r] == dp[l][m] + dp[m + 1][r]:
  37. stack.append((l, m))
  38. stack.append((m + 1, r))
  39. break
  40.  
  41. print(''.join(res))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement