6171: BZOJ2171：K凹凸序列

一个序列的第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，符合要求

提示

没有写明提示

题目来源

版权所有者：范浩强