Фарбування камінців#5

Фарбування камінців (Розбір)

Рішення для :

Давайте перебирати колір, в який будуть пофарбовані всі камінці в кінці. Щоб знайти мінімальну кількість пофарбувань для певного кольору можна слідувати такому жадібному алгоритму:

  • якщо колір камінця який ми перебираємо то йдемо далі;

  • інакше, фарбуваємо теперіншій на наступний камінці в колір який перебираємо.

повне рішення:

Припустимо ми перебираємо колір . За яку мінімальну кількість операцій можна пофарбувати відрізок [l,r] де крайні камінці кольору , та інших камінців крім крайніх кольору нема? З алгоритму до рішення n\le 1000 випливає відповідь \lfloor \frac{r-l}{2} \rfloor.

Можемо розбити масив на такі відрізки, та загальна відповідь для кольору це сума відповідей на кожному відрізку. (Також потрібно не забути що можливо треба пофарбувати префікс і суфікс).

Отже рішення, це обчислювати кожен колір окремо. Для кольору ми навели алгоритм з складністю де це кількість входень числа в масив. Сумарно для всіх кольорів рішення з складністю .