ACMP 503

Материал из Олимпиадное программирование в УлГТУ
Версия от 21:48, 31 июля 2015; Ctrlalt (обсуждение | вклад) (Новая страница: «== Ссылка на задачу == * [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(2N × N).

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

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