K凹凸序列

时间限制:20s      空间限制:259MB

题目描述

一个序列的第1,3,5...项被称作奇数项,第2,4,6...项被称作偶数项。一个序列A[1..n]被称作ZigZag序列当且仅当以下两个条件中的一个(或两个)成立: 1)除了首项,所有的奇数项都比它的前项小且所有的偶数项都比它的前项大。 2)除了首项,所有的奇数项都比它的前项大且所有的偶数项都比它的前项小。一个序列A[1..n]被称作K凹凸序列当且仅当它的最长ZigZag子序列(不一定是连续子序列)的长度不超过K。现在有一个序列A[1..n],每次可以花费1的代价使得A中的某一项增加或减少1。我们的目的是花费最少的代价让它成为K凹凸序列。


输入格式

输入的第一行包含两个正整数,分别表示数列A[1..N]的长度N和K。接下来的N行每行一个自然整数,依次表示数列的项。前1个测试点满足:K=1,N≤20000 第2~8个测试点满足:K=2,N≤20000 第9~15个测试点满足:K=3,N≤20000 第16~20个测试点满足:K≤10,N≤1000 所有测试点满足:A[i]≤50000


输出格式

输出一个整数,表示最小代价。


样例输入

9 3
1
2
3
6
9
8
7
4
5

样例输出

1
【样例说明】
把最后一项减小1,得到序列
1 2 3 6 9 8 7 4 4
它的最长ZigZag子序列之一是
1 9 4
长度为3,符合要求

提示

没有写明提示


题目来源

版权所有者:范浩强