Виставка#477

Виставка (Розбір)

Автор, розробник, автор розбору: Ілля Пермяков

Помітимо, що фактично в задачі потрібно знайти мінімальну суму на двох відрізках однакової довжини, таких що між ними є хоча б один елемент. Нехай ця сума дорівнюватиме , а сума усіх елементів масиву дорівнюватиме . Тоді якщо T > 0, то відповіддю буде , інакше відповіддю буде S - T. Тепер залишилось навчитись знаходити суму .

Спочатку зафіксуємо  — довжину двох відрізків. Тепер для кожного індексу (x \leq i \leq n-x+1) порахуємо два значення:

  • Мінімальна сума на відрізку довжини , найправіший елемент якого має індекс . Позначимо її за A_{i, x}.

  • Мінімальна сума на відрізку довжини , лівіший елемент якого має індекс . Позначимо її за B_{i, x}.

Ці значення можна порахувати, наприклад, за допомогою префіксних та суфіксних мінімумів.

Тепер зафіксуємо індекс (x < y < n-x+1) — це буде один з елементів, що знаходиться між двома відрізками. Помітимо, що якщо у відповіді знаходиться між двома частинами завіси, то ліву частину оптимально буде розмістити на такому відрізку лівіше , що має мінімальну суму. Аналогічно розмістимо праву завісу. Сума елементів при оптимальному розміщенні лівої частини завіси буде дорівнювати A_{y-1, x}, а правої — B_{y+1, x}. Отже, для фіксованого та фіксованого , сума дорівнюватиме A_{y-1, x} + B_{y+1, x}. Тепер залишилось перебрати та , і серед усіх таких варіантів обрати мінімальний.

Сумарний час роботи рішення — O(n^2).