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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
(Новая страница: «== Ссылка на задачу == * [http://acmp.ru/?main=task&id_task=646 ACMP #646 — Сладкие забавы] == Комментарии == Вид…»)
 
Нет описания правки
Строка 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).