Ctrlalt в 21:20, 17 декабря 2014

2014-12-17T21:20:54Z

← Предыдущая версия		Версия от 21:20, 17 декабря 2014
Строка 15:		Строка 15:

	[[Category: Сборник задач: ACMP]]		[[Category: Сборник задач: ACMP]]
	[[Category: Задачи: ~~Динамические~~ программирование — три параметра]]		[[Category: Задачи: Динамическое программирование — три параметра]]

Ctrlalt: Новая страница: «== Ссылка на задачу == * [http://acmp.ru/?main=task&id_task=566 ACMP #566 — Халява] == Комментарии == Вид подзада…»

2014-12-17T21:20:09Z

Новая страница: «== Ссылка на задачу == * [http://acmp.ru/?main=task&id_task=566 ACMP #566 — Халява] == Комментарии == Вид подзада…»

Новая страница

== Ссылка на задачу ==
* [http://acmp.ru/?main=task&id_task=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<sup>3</sup>).

[[Category: Сборник задач: ACMP]]
[[Category: Задачи: Динамические программирование — три параметра]]

ACMP 566 - История изменений

Ctrlalt в 21:20, 17 декабря 2014

Ctrlalt: Новая страница: «== Ссылка на задачу == * [http://acmp.ru/?main=task&id_task=566 ACMP #566 — Халява] == Комментарии == Вид подзада…»