ACMP 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^N × N).

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

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