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

2015-07-31T21:48:36Z

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

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

== Ссылка на задачу ==
* [http://acmp.ru/?main=task&id_task=503 ACMP #503 — Бюро путешествий]

== Комментарии ==

* Вид подзадачи: dCost[mask] — ответ на задачу только для планет, заданных маской mask; dFirst[mask] — номер первой планеты в маршруте, обеспечивающем ответ dCost[mask].
* Рекуррентная формула: При расчёте dCost[mask] перебираем все планеты из mask. Пусть на первом месте находится i-я планета, тогда остальные заданы маской mask' = mask & ~(1 << i).
: В данном случае величина штрафа равна dCost[mask'] + (planet[i].cFrom * pPlanetsIn[mask']) + (planet[i].pFrom * cPlanetsIn[mask']) + XTo[mask'], где XTo[mask'] — количество чатлан, прилетающих на планеты mask' (cTo[mask']), если планета i — пацакская, либо количество пацаков, прилетающих на планеты mask' (pTo[mask']), если планета i — чатланская. dCost[mask] определяется как минимальный из возможных штрафов.
: Значения cPlanetsIn[], pPlanetsIn[], cTo[], pTo[] для всех возможных масок нужно посчитать заранее.
* База рекурсии: dCost[0] = 0.
* Вид ответа: dCost[(1 << n) - 1], маршрут восстанавливается по dFirst[]. Сложность O(2<sup>N</sup> × N).

Для удовлетворения лимита памяти элементы dCost[], cTo[] и pTo[] должны иметь тип short, dFirst[] — тип char. Значения cPlanetsIn[] и pPlanetsIn[] можно не сохранять, а пересчитывать за O(N) для каждой mask (но не отдельно для всех mask').

Второй пример содержит русские буквы 'С'.

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

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

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