Сглаживание пикселей

Дана строка пикселей: список чисел от 0 до 255 (до 40 пикселей). Строка гладкая, если любые два соседних пикселя отличаются не больше чем на max_gap; пустая строка и строка из одного пикселя гладкие. Разрешены три операции в любом количестве и порядке:

• удалить любой пиксель за delete_cost (его соседи становятся соседями);
• вставить пиксель любого значения от 0 до 255 в любое место (в начало, в конец или между двумя пикселями) за insert_cost;
• изменить значение пикселя на любое от 0 до 255; цена равна модулю разности старого и нового значения.

Все цены и max_gap — целые числа от 0 до 255. Верните наименьшую суммарную цену операций, после которых строка станет гладкой.

Пример: delete_cost = 100, insert_cost = 1, max_gap = 5, [1, 50, 7] → 17 (вставить 9 пикселей между 1 и 50 и 8 пикселей между 50 и 7).

Источник: Coding Competitions Archive, codejam/2010/round_1a/make_it_smooth · © Google LLC · Apache-2.0 · условие переведено и дополнено