ACMP 646: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (Новая страница: «== Ссылка на задачу == * [http://acmp.ru/?main=task&id_task=646 ACMP #646 — Сладкие забавы] == Комментарии == Вид…») |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 13: | Строка 13: | ||
[[Category: Сборник задач: ACMP]] | [[Category: Сборник задач: ACMP]] | ||
[[Category: Задачи: Динамическое программирование — параметр | [[Category: Задачи: Динамическое программирование — префикс, параметр]] | ||
Версия от 06:24, 31 декабря 2014
Ссылка на задачу
Комментарии
Вид подзадачи: d[i][j] — количество способов набрать i конфет, используя коробки 0..j.
Рекуррентная формула: d[i][j] = d[i][j - 1] + d[i - w[j]][j - 1].
База рекурсии: d[0][0] = 1.
Вид ответа: max(0, 2n - 2 × ∑d[i][n]), где i ∈ 0..(k - 1). Сложность O(N2).