Офіс для домашніх тварин#12996

Офіс для домашніх тварин (Розбір)

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

Отже кожна позиція має лише три кандидати — a_i - 1, a_i та a_i + 1 — і задача стає динамічним програмуванням уздовж масиву: — мінімальна кількість операцій на префіксі за умови, що на -й позиції стоїть -й кандидат. Перехід перебирає три кандидати попередньої позиції та відкидає ті, значення яких збігається з поточним:

dp[i][t] = |t\text{-й зсув}| + \min_{s\,:\ \text{значення}(i-1,s) \ne \text{значення}(i,t)} dp[i-1][s].

Відповідь — мінімум по трьох станах останньої позиції. Зверніть увагу, що значення можуть виходити за межі [0, 10^9] (наприклад, масив [0,0,0,0] вигідно перетворити на [0,1,-1,0]), і це дозволено умовою.

Складність: з константою .

Для цього етапу офіційного розбору опубліковано не було; цей текст написано для архіву за розв'язком, який перевірено на задачі.