3687: 变幻(第三轮01)
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
如果数组 a 中有任意一个点 i 满足ai−1 > ai &&ai < ai+1，我们则称这个点 i 为 “山谷点”。注意，数组中第一个元素和最后一个元素永远不可能为山谷点。
一个数组的价值是所有山谷点之和。
至多修改 k 次数组，每次修改可以任选一个位置，使得这个位置上的数字变得 比原来更小。你希望数组的价值最大，求最大价值。
输入
第一行包含两个正整数 n, k，意义如题面所示
接下来一行包含 n 个正整数，表示数组中的元素 ai 。
输出
输出一行一个正整数表示答案。
样例输入 复制
3 1
5 6 7样例输出 复制
4提示
【样例 1 输入】
3 1
5 6 7
【样例 1 输出】
4
【样例 1 说明】
对于原数组来说，没有山谷点， 所以价值为 0。我们可以将第二个位置改为 4， 这样原数组变为 [5,4,7]，其中第二个位置为山谷点。此时总价值为 4。
【数据范围】
对于 20% 的数据，有 1 ≤ n ≤ 20。
对于另外 20% 的数据，有 k = 1。
对于另外 20% 的数据，有 k = 2。
对于 100% 的数据，有1 ≤ k ≤ n ≤ 2000,1 ≤ ai ≤ 10^9 。