Нульові перельоти. Ціна перельоту — |i-j|\cdot|a_i-a_j|, тож між двома частинами однакової висоти переліт безкоштовний. Оскільки висоти не перевищують , усі частини розбиваються щонайбільше на груп, і всередині групи ми пересуваємось задарма. Задача одразу стискається з 10^5 до об'єктів.
Ціна між групами. Для груп із висотами h_u і h_v множник |h_u - h_v| однаковий для всіх пар, тому найдешевший переліт — це
Мінімальну різницю індексів рахуємо одним проходом: ідемо зліва направо й тримаємо для кожної висоти останню позицію, де вона траплялась, — .
Замикання за найкоротшими шляхами. Обережно: ця ціна не задовольняє нерівність трикутника. Наприклад, дострибнути з висоти на висоту напряму може бути дорожче, ніж через проміжну . Тому спершу проженемо Флойда–Уоршелла по вершинах і отримаємо справжні найкоротші відстані.
Обхід усіх груп. Тепер треба, стартувавши з групи, якій належить перша частина, відвідати всі групи. У метричному замиканні повторні відвідування нічого не дають, отже шукаємо найкоротший гамільтонів шлях — класична динаміка за бітовими масками:
відповідь — мінімум \mathrm{dp}[\text{повна маска}][u]. Це \mathcal{O}(2^{18}\cdot 18^2), тобто менш ніж 10^8 простих операцій.
Окремі випадки: якщо всі частини однакової висоти (або n = 1), відповідь . Ціни сягають 10^5 \cdot 17, а сума — значно більше, тож рахуйте у -бітних.