Ділимо масив#509

Ділимо масив (Розбір)

Автор, розробник, автор розбору: Андрій Столітній

В умові задачі написано, що нам треба, щоб кожен підвідрізок довжини більше ніж 1 кожного з фінальних масивів мав невід'ємну суму. Можна помітити, що достатньо, щоб всі підвідрізки довжиною та мали невід'ємну суму. Тому що кожний відрізок довжини більше ніж можна розбити на підвідрізки довжини і , а якщо вони всі мають невід'ємну суму, то весь відрізок має невід'ємну суму.

Також розбиття масиву на менші масиви можна робити неявно, усуваючи елементи з масиву. Будемо підтримувати значення динамічного програмування, де dp_{i,j} буде означати максимальну кількість елементів, яку ми можемо залишити з префіксу довжини , та ми залишили останні елементів, тобто , i-1, ..., i-j+1. Тоді, коли додаємо новий елемент, ми можемо або залишати його, або прибирати. Так як ми не розглядаємо підвідрізки довжини більше, ніж , то можемо зробити стани dp_{i,0}, dp_{i,1}, dp_{i,2}, dp_{i,3} —

  • не взяли елемент ,

  • взяли елемент , не взяли i-1,

  • взяли , i-1, не взяли i-2,

  • взяли , i-1, i-2, або більше.

Тоді можна зробити такі переходи:

dp_{i,0} = \max \left( dp_{i-1,0}, \; dp_{i-1,1}, \; dp_{i-1,2}, \; dp_{i-1,3} \right)
dp_{i,1} = dp_{i-1,0} + 1
dp_{i,2} = dp_{i-1,1} + 1,\ \text{якщо } a_i + a_{i-1} \ge 0
dp_{i,3} = \max \left( dp_{i-1,2}, \; dp_{i-1,3} \right) + 1,\ \text{якщо } a_i + a_{i-1} \ge 0\ \text{і } a_i + a_{i-1} + a_{i-2} \ge 0

Тоді відповіддю буде

n - \max \left( dp_{n,0}, \; dp_{n,1}, \; dp_{n,2}, \; dp_{n,3} \right).

Загальна складність: .