Задача №2862. Последовательность
Последовательность чисел называется монотонно убывающей, если для любого номера \(i\) (кроме последнего) выполняется \(A_i > A_{i+1}\). Последовательность чисел называется монотонно возрастающей, если для любого номера \(i\) (кроме последнего) выполняется \(A_i < A_{i+1}\). Последовательность называется монотонной, если она или монотонно убывающая, или монотонно возрастающая. Дана последовательность \(A_i\) из \(N\) чисел. За одно действие каждый элемент последовательности можно либо увеличивать на 1, либо уменьшать на 1. Требуется изменить последовательность так, чтобы в ней содержалось ровно \(K\) монотонных непересекающихся последовательностей (один элемент тоже является последовательностью) за минимально возможное количество действий.
В первой строке входных данных содержатся числа \(N\) и \(K\) --- количество элементов в последовательности и сколько должно быть монотонный частей, соответственно (\(1 \leq N \leq 50, 1 \leq K \leq 25\)). В слеюущей строке содержатся \(N\) чисел --- элементы последовательности, каждое число по модулю не превосходит \(20\,000\,000\).
Одно число, ответ на задачу
4 1 1 1 1 1
4
6 2 1 2 3 4 5 6
0