Задача №381. Последовательность
Последовательность чисел монотонно убывающая если для любого i элемента (кроме последнего )выполняется Ai > Ai+1. Последовательность чисел монотонно возрастающая если для любого i элемента (кроме последнего )выполняется Ai < Ai+1. Последовательность монотонная если она или монотонно убывающая или монотонно возрастающая. Дана последовательность Ai из n чисел. Каждый элемент последовательности можно увеличивать или уменьшать. Требуется изменить последовательность так что бы в ней содержалось K монотонных непересекающихся последовательностей. (один элемент тоже последовательность). Т.к. преобразований бесконечно много то нужно найти такое преобразование чтобы сумма разностей по модулю конечного значения Ai и начального значения Ai была минимальна.
В первой строчке n,k n- количество элементов в последовательности, k сколько должно быть монотонных последовательностей. Во второй строчке n чисел через пробел - сама последовательность(каждое число по модулю меньше 20,000,000)
Одно число, ответ на задачу.
4 1 1 1 1 1
4
6 1 1 2 3 3 2 1
9