ACMP 646

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

• 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, 2ⁿ - 2 × ∑d[i][n]), где i ∈ 0..(k - 1). Сложность O(N²).