Модуль: Паттерны в динамическом программировании - 2


Задача

1 /5


Игра-заливка

Теория Нажмите, чтобы прочитать/скрыть

Дисклеймер: способ, описанный ниже, не является универсальным, однако зачастую может решить задачу или помочь прийти к правильному решению.

Если в задаче вас просят оптимальным образом уничтожить/схлопнуть/объединить (или похожее) массив, то стоит попробовать решить ее с помощью динамического программирования на подотрезках.

Заведем dp[l][r] - оптимальный ответ для подотрезка с индексами от l до r. Пересчет динамики сильно зависит от задачи, но есть следующие общие идеи:

1) Посмотреть на крайние элементы l и r. Если они совпадают или еще как-либо комплементируют, то, скорее всего, можно будет обновить значение dp[l][r] через dp[l+1][r-1]. Иначе через dp[l][r-1] или dp[l+1[r].

2) Часто бывает, что отрезок [l;r] нельзя представить через единую конструкцию. Тогда необходимо рассмотреть все возможные разделы этого подотрезка на две части, то есть перебрать элемент k от l до r-1 и пересчитывать dp[l][r] через dp[l][k] и dp[k+1][r]. В более маленьких подотрезках также перебирались эти разделы, поэтому на самом деле учитываются варианты разбиения подотрезка [l;r] не только на две части, а на любое их число.
 

Задача

Вам дана полоска из клетчатой бумаги из n раскрашенных квадратов, пронумерованных от 1 до n слева направо. Квадрат под номером i изначально покрашен в цвет ci.

Скажем, что квадраты i и j лежат в одной компоненте, если c= cj и c= ck для всех k, удовлетворяющих i < k < j. Иначе говоря, все квадраты на отрезке от i до j должны иметь одинаковый цвет.
Например, у полоски [3,3,3] есть 1 компонента связности, а у [5,2,4,4] их 3.

Игра «заливка» играется на этой полоске следующим образом:
В начале игры вы выбираете один произвольный стартовый квадрат (это не считается за ход).
Затем, в каждый ход, вы меняете цвет компоненты связности, содержащей стартовый квадрат на любой другой цвет.

Выясните минимальное количество ходов, которое нужно, чтобы перекрасить всю полоску в один цвет.

Входные данные:
Первая строка содержит одно целое число n (1 ≤ n ≤ 5000) — количество квадратов.

Вторая строка содержит целые числа c1,c2,…,cn (1 ≤ ci ≤ 5000) — изначальные цвета квадратов.

Выходные данные:
Выведите одно целое число — минимальное количество ходов, которое нужно сделать.

Примеры:
 
Входные данные Выходные данные
4
5 2 2 1
2
8
4 5 2 2 1 3 5 5
4
1
4
0

Пояснение:
Один из оптимальных способов в первом примере: [5, 2, 2, 1] -> [5, 2, 2, 2] -> [5, 5, 5, 5]


time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w641
Комментарий учителя