ACMP 646

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Версия для печати больше не поддерживается и может содержать ошибки обработки. Обновите закладки браузера и используйте вместо этого функцию печати браузера по умолчанию.

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

Комментарии

Вид подзадачи: 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).