#P2171. K凹凸序列

    ID: 1195 传统题 2000ms 259MiB 尝试: 51 已通过: 30 难度: 8 上传者: 标签>CF2500提高+/省选-Slope Trick二叉堆线性 DP前后缀分解滚动数组中位数最小化绝对偏差和版权所有者:范浩强

K凹凸序列

题目描述

一个序列的第 1,3,5…1,3,5\dots 项被称作奇数项,第 2,4,6…2,4,6\dots 项被称作偶数项。

一个序列 a1…na_{1\dots n} 被称作 ZigZag 序列当且仅当以下两个条件中的一个(或两个)成立:

  1. 除了首项,所有的奇数项都比它的前项小且所有的偶数项都比它的前项大。
  2. 除了首项,所有的奇数项都比它的前项大且所有的偶数项都比它的前项小。

一个序列 a1…na_{1\dots n} 被称作 kk 凹凸序列当且仅当它的最长 ZigZag 子序列(不一定是连续子序列)的长度不超过 kk。现在有一个序列 a1…na_{1\dots n},每次可以花费 11 的代价使得 aa 中的某一项增加或减少 11。我们的目的是花费最少的代价让它成为 kk 凹凸序列。

输入格式

输入的第一行包含两个正整数,分别表示数列 a1…na_{1\dots n} 的长度 nn 和 kk。

接下来的 nn 行每行一个自然整数,依次表示数列的项。

输出格式

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

样例输入

9 3
1
2
3
6
9
8
7
4
5

样例输出

1

样例说明

把最后一项减小 11,得到序列 1 2 3 6 9 8 7 4 4,它的最长 ZigZag 子序列之一是 1 9 4,长度为 33,符合要求。

数据规模与约定

前 11 个测试点满足:k=1k=1,n≤2×104n\leq 2\times 10^4。

第 2∼82\sim 8 个测试点满足:k=2k=2,n≤2×104n\leq 2\times 10^4。

第 9∼159\sim 15 个测试点满足:k=3k=3,n≤2×104n\leq 2\times 10^4。

第 16∼2016\sim 20 个测试点满足:k≤10k\leq 10,n≤103n\leq 10^3。

所有测试点满足:0≤ai≤5×1040\leq a_i\leq 5\times 10^4。

题目来源

版权所有者:范浩强