Гірський хребет#40

Гірський хребет (Розбір)

Нульові перельоти. Ціна перельоту — |i-j|\cdot|a_i-a_j|, тож між двома частинами однакової висоти переліт безкоштовний. Оскільки висоти не перевищують , усі частини розбиваються щонайбільше на груп, і всередині групи ми пересуваємось задарма. Задача одразу стискається з 10^5 до об'єктів.

Ціна між групами. Для груп із висотами h_u і h_v множник |h_u - h_v| однаковий для всіх пар, тому найдешевший переліт — це

d(u,v) \;=\; |h_u - h_v| \cdot \min_{\substack{a_i = h_u,\ a_j = h_v}} |i - j|.

Мінімальну різницю індексів рахуємо одним проходом: ідемо зліва направо й тримаємо для кожної висоти останню позицію, де вона траплялась, — .

Замикання за найкоротшими шляхами. Обережно: ця ціна не задовольняє нерівність трикутника. Наприклад, дострибнути з висоти на висоту напряму може бути дорожче, ніж через проміжну . Тому спершу проженемо Флойда–Уоршелла по вершинах і отримаємо справжні найкоротші відстані.

Обхід усіх груп. Тепер треба, стартувавши з групи, якій належить перша частина, відвідати всі групи. У метричному замиканні повторні відвідування нічого не дають, отже шукаємо найкоротший гамільтонів шлях — класична динаміка за бітовими масками:

\mathrm{dp}[\mathrm{mask}][u] = \text{мінімальна ціна, якщо відвідано групи } \mathrm{mask} \text{ і ми в } u,

відповідь — мінімум \mathrm{dp}[\text{повна маска}][u]. Це \mathcal{O}(2^{18}\cdot 18^2), тобто менш ніж 10^8 простих операцій.

Окремі випадки: якщо всі частини однакової висоти (або n = 1), відповідь . Ціни сягають 10^5 \cdot 17, а сума — значно більше, тож рахуйте у -бітних.