Winter Games
Турнир за Купата на Декана, 2011
Time Limit: 0.4s, Memory Limit: 64MiB
Зимата идва, а с нея и зимните спортове. Ели и Крис стартираха собствен бизнес, който включва създаването на комплекс ски писти. След дълго мислене се спряха на девиза "Ние ще ви изпързаляме най-добре".

Първата инвестиция на фирмата им беше закупуването на малка планина с дължина N километра. Тъй като пистите, които правят, са сравнително прави, можем да си представим планината като 2D обект, описан чрез N числа - височината на планината в отрези по един километър. Двете момичета са решили да разделят планината на K части, които да превърнат в писти с дължина цяло число, не по-малко от един километър. За да гарантират удоволствие при карането на ски, Ели и Крис са решили да направят пистите изцяло спускащи се или изцяло изкачващи се (тоест пак спускащи се, но от другата страна), като намалят или увеличат височината на планината в някои нейни части. Това, за нещастие, е трудоемка задача и те се чудят по какъв начин да го направят с минимално усилия.

По формално, дадена ви е редица от N цели числа и от вас се иска да я разбиете на K строго монотонно-намаляващи или нарастващи подредици от последователни елементи. За целта можете да намаляте или увеличавате числата. Целта е да постигнете това с минимална промяна на числата - тоест сумата от абсолютните стойности на разликите между началните и крайните стойности на числата да е минимална.

Една редица от числа се нарича строго монотонно-нарастваща ако всеки нейн член (с изключение на първия) е по-голям от предходния. Обратно, ако всеки нейн член (с изключение на първия) е по-малък от предходния, редицата се нарича строго монотонно-намаляваща. Редица с един елемент е както строго монотонно растяща, така и строго монотонно намаляваща (и може да се ползва за писта).

От вас се иска да изчислите минималните усилия, които трябва да вложат в промяната на планината, за да може тя да се разбие на K непресичащи се подредици от последователни числа. Тъй като Ели и Крис са давали пари за планината, те искат да я използват цялата (тоест не може да остане част от нея, която да не е част от някоя писта).
Вход
На първия ред на стандартния вход ще съдържа две цели числа N и K – съответно дължината на планината и броя части, на които момичетата искат да я разделят. На втория ред на всеки тест ще са зададени по N цели числа A1, A2, ..., AN – височината на планината в нейните отрязъци.
Изход
На един единствен ред на стандартния изход изведете едно цяло число – минималното усилие, което двете приятелки трябва да вложат за приготвянето на пистите.
Ограничения
  • 1 ≤ KN ≤ 50
  • -20,000,000 ≤ Ai ≤ 20,000,000
Примерен Вход Примерен Изход
5 2 3 1 5 5 2 1
11 3 7 3 4 2 5 1 2 2 4 6 -2 7
3 1 0 0 0 2
В първия пример можем да променим редицата на {3, 1, 5, 4, 2} с усилие 1, като после я разбием на пистите {3, 1} и {5, 4, 2}. Във втория пример едно възможно разбиване би било {7, 5, 4, 2, 1}, {1, 2, 3, 4, 6}, {-2}, водещо до усилие 7. В третия пример можем да превърнем редицата в {-1, 0, 1} с усилие 2.
Мрън!