ACMP 176: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (Новая страница: «== Ссылка на задачу == * [http://acmp.ru/?main=task&id_task=176 ACMP #176 — Скобочки] == Комментарии == Вид подза…») |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 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]] | |||
== Комментарии == | == Комментарии == | ||
| Строка 13: | Строка 16: | ||
[[Category: Сборник задач: ACMP]] | [[Category: Сборник задач: ACMP]] | ||
[[Category: Задачи: Длинная арифметика]] | [[Category: Задачи: Длинная арифметика]] | ||
[[Category: Задачи: | [[Category: Задачи: Динамическое программирование — два параметра]] | ||
Текущая версия от 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).