Обміни з максимальною сумою#12951

Обміни з максимальною сумою (Editorial)

Нехай ми хочемо замінити елементів з лівої частини на елементів з правої. Відповідь на задачу тоді буде: сума в лівій частині - сума елементів, які ми заміняємо в лівій частині + сума елементів, які ми заміняємо в правій частині. Можна показати, що однією з оптимальних послідовностей операцій буде:

Порахуємо динаміку dp1_{i, j} — мінімальна сума елементів в лівій частині, якщо ми зробили ходів, щоб виконати перший крок. Аналогічно порахуємо динаміку dp2_{i, j} — максимальна сума елементів в правій частині, якщо ми зробили ходів, щоб виконати другий крок. Третій крок зробити просто. Таку динаміку можна рахувати за О(n^4).

Об’єднати такі дві динаміки можна за O(n^5), але це повільно. Модифікуємо трохи другу динаміку наступним чином: dp_{i, j} — Нехай ми зробили перший крок і виконуємо другий. Нам треба ще елементів досунути в правій частині та ми зробили вже сумарно кроків. Ми будемо її перераховувати за допомогою . Таку динаміку можна рахувати за O(n^4) і вона зразу покриє перші два кроки. Оскільки нам треба зробити щонайбільше кроків, то треба взяти ще максимум на префіксі.