Advertisement
Guest User

Untitled

a guest
Jan 22nd, 2019
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.85 KB | None | 0 0
  1. #include<iostream>
  2. #include<string>
  3. #include<vector>
  4.  
  5. using namespace std;
  6.  
  7. int main() {
  8.  
  9. string s;
  10. cin >> s;
  11.  
  12. long long n = s.size();
  13. vector < vector < long long > > a(n + 1, vector < long long > (n + 1, 0));
  14.  
  15. a[0][0] = 1;
  16.  
  17. for (int i = 1; i <= n; i++) {
  18. for (int j = 0; j <= n; j++) {
  19. if (s[i - 1] == ')') {
  20. a[i][j] = a[i - 1][j + 1];
  21. continue;
  22. }
  23. if (s[i - 1] == '(') {
  24. if (j - 1 >= 0) {
  25. a[i][j] = a[i - 1][j - 1];
  26. }
  27. continue;
  28. }
  29.  
  30. if (j - 1 >= 0) {
  31. a[i][j] = a[i - 1][j + 1] + a[i - 1][j - 1];
  32. }
  33. else {
  34. a[i][j] = a[i - 1][j + 1];
  35. }
  36. }
  37. }
  38. cout << a[n][0];
  39. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement