ACMP 176: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
== Ссылка на задачу ==
== Ссылка на задачу ==
* [http://acmp.ru/?main=task&id_task=176 ACMP #176 — Скобочки]
* [http://acmp.ru/?main=task&id_task=176 ACMP #176 — Скобочки]
== Похожие задачи ==
* [[РОИ 2006-2007, региональный этап, A]]


== Комментарии ==
== Комментарии ==

Текущая версия от 07:12, 2 января 2015

Ссылка на задачу

Похожие задачи

Комментарии

Вид подзадачи: d[i][j] — количество последовательностей с i открывающими скобками глубиной не более j.

Рекуррентная формула: d[i][j] = ∑(d[k][j - 1] × d[i - 1 - k][j]), где k ∈ 0..(i - 1).

База рекурсии: Если i = 0, то d[i][j] = 1; если i ≠ 0 и j = 0, то d[i][j] = 0.

Вид ответа: d[n][k] - d[n][k - 1]. Сложность O(N3).