Advertisement
Guest User

Untitled

a guest
Sep 19th, 2017
654
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.05 KB | None | 0 0
  1. // imslavko@gmail.com
  2. #include <cstdio>
  3. #include <cstring>
  4.  
  5. char s[100];
  6. int a[100][100], n;
  7. int main() {
  8.     scanf("%s", s + 1); // я начал строку с 1, чтобы было проще
  9.     a[0][0] = 1; // 1 способ для нулевой строки с нулевым балансом
  10.     n = strlen(s + 1); // n = |s|, размер строки
  11.     for (int i = 1; i <= n; i++) // для каждого символа
  12.         for (int j = 0; j < 85; j++) { // для каждого баланса
  13.             if (s[i] == '(' || s[i] == '?') // баланс увеличивается
  14.                 a[i][j + 1] += a[i - 1][j];
  15.             if (s[i] == ')' || s[i] == '?') // баланс уменьшается
  16.                 if (j - 1 >= 0) // надо проверить, чтобы баланс был больше нуля
  17.                     a[i][j - 1] += a[i - 1][j];
  18.         }
  19.     printf("%d\n", a[n][0]); // овет - сколько таких с нулевым балансом в конце, так как нам нужны только правильные последовательности
  20.     return 0;
  21. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement