ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 102779
Тема:    [ Динамическое программирование: классические задачи ]
Сложность: 3
Классы:
Название задачи: Восстановление скобок .
В корзину
Прислать комментарий

Условие

Задан шаблон, состоящий из круглых скобок и знаков вопроса. Требуется определить, сколькими способами можно заменить знаки вопроса круглыми скобками так, чтобы получилось правильное скобочное выражение.

Входные данные

Первая строка входного файла содержит заданный шаблон длиной не более 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. Придумайте, как обойтись в этой задаче одномерным массивом.

Источники и прецеденты использования

книга
предмет информатика
Автор Беров В., Лапунов А., Матюхин В., Пономарев А.
Название Особенности национальных задач по информатике
Издательство Триада-С
Год издания 2000
глава
Номер 1
Название Динамическое программирование
Задача
Номер 2

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .