ACMP 566

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

• ACMP #566 — Халява

Комментарии

Вид подзадачи: d1[p][q][r] — максимальное количество футболок за p крышек с одной звездой, q крышек с двумя звёздами и r крышек с тремя звёздами; d2[p][q][r] — максимальное количество звёзд на лишних крышках при таком обмене.

Рекуррентная формула: {d1[p][q][r], d2[p][q][r]} = max({x1, x2}, {y1, y2}, {z1, z2}).

Если p < 1, то {x1, x2} = {0, q * 2 + r * 3}, иначе если d2[p - 1][q][r] + 1 >= k, то {x1, x2} = {d1[p - 1][q][r] + 1, 0}, иначе {x1, x2} = {d1[p - 1][q][r], d2[p - 1][q][r] + 1}.

Если q < 1, то {y1, y2} = {0, p * 1 + r * 3}, иначе если d2[p][q - 1][r] + 2 >= k, то {y1, y2} = {d1[p][q - 1][r] + 1, 0}, иначе {y1, y2} = {d1[p][q - 1][r], d2[p][q - 1][r] + 2}.

Если r < 1, то {z1, z2} = {0, p * 1 + q * 2}, иначе если d2[p][q][r - 1] + 3 >= k, то {z1, z2} = {d1[p][q][r - 1] + 1, 0}, иначе {z1, z2} = {d1[p][q][r - 1], d2[p][q][r - 1] + 3}.

База рекурсии: d1[0][0][0] = d2[0][0][0] = 0.

Вид ответа: d1[a][b][c]. Сложность O(N³).