|
Название задачи: Восстановление скобок . |
 |
Условие
Задан шаблон, состоящий из круглых скобок и
знаков вопроса. Требуется определить,
сколькими способами можно заменить знаки
вопроса круглыми скобками так, чтобы
получилось правильное скобочное выражение.
Входные данные
Первая строка входного файла содержит
заданный шаблон длиной не более 80 символов.
Выходные данные
Выведите в выходной файл искомое
количество способов. Исходные данные будут
таковы, что это количество не превзойдет 2·109
.
Пример входного файла
????(?
Пример выходного файла
2
Решение
Скачать архив тестов и решений
Рассмотрим скобочную последовательность s длины n. Пусть ci(s) равняется
разности между общим количеством открывающих и закрывающих скобок
среди первых i символов этой последовательности. Ясно, что s является
правильным скобочным выражением тогда и только тогда, когда ci(s)
≥ 0 для всех i от 1 до n и, кроме того, cn(s) = 0.
Обозначим через F(k, c) количество скобочных последовательностей s длины k, подходящих под первые k символов шаблона и таких, что ci(s) ≥ 0 для всех i от 1 до k, а ck(s) = c. Очевидно, что ответом на исходную задачу будет являться число F(N, 0), где N - длина заданного шаблона.
Рассмотрим задачу вычисления чисел F(k, c). Если k-й символ шаблона -открывающая скобка, то F(k, c) = F(k-1, c-1), если закрывающая, то F(k, c) = F(k-1, c+1). Если же это знак вопроса, то на его место можно поставить как открывающую, так и закрывающую скобку, и F(k, c) = F(k-1, c-1) + F(k-1, c+1).
Получив эту формулу, задаем граничные значения F(0, c) = 0, F(k, -1) = 0,
F(0, 0) = 1 и двумя вложенными циклами (внешний – по k, а внутренний – по
c) последовательно вычисляем искомые числа F(k, c) для всех k от 1 до N и всех
c от 0 до N. Значение F(N, 0) выводим в качестве ответа.
Упражнения
1. Все ли из чисел F(k, c) нам нужны для вычисления значения F(N, 0)?
2. Придумайте, как обойтись в этой задаче одномерным массивом.
