[USACO06MAR] Ski Lift G

题目描述

科罗拉多州的山脉是二维平面上的一条折线。这条折线由 $N$ 个端点,$N−1$ 段线段组成,第 $i$ 个端点的横坐标就是 $i$,纵坐标是 $H_i$,纵坐标代表高度,也可以称为海拔。 罗恩打算为奶牛建造一个滑雪场,为此要在山脉上规划一条缆车线路。缆线也是一条折线,由若干段缆绳组成,起点在山脉的第一个端点,终点在最后一个端点。每段缆绳可以贴着山脉的轮廓,也可以悬浮于空中,跳过山脉上几个海拔低的端点。每段缆绳的水平跨度有限制,不能超过给定的整数 $K$。罗恩需要在每段缆绳的端点处修建支柱,用来固定缆绳。 请帮助他规划一下,选择在山脉的哪些端点上修建,才能使得支柱数量最少?注意,根据题意,起点和终点上是一定要修建的。

输入输出格式

输入格式


第一行:两个整数 $N$ 和 $K$。 第二行到第 $N + 1$ 行,第 $i+1$ 行有一个整数 $H_i$。

输出格式


一行一个整数表示最少需要修建的支柱数量。

输入输出样例

输入样例 #1

13 4
0
1
0
2
4
6
8
6
8
8
9
11
12

输出样例 #1

5

说明

解释 最优方案是把支柱设在 $1,5,7,9,13$。$5$ 不能直接连 $9$,因为 $9$ 的海拔较高,$1$ 不能直接连 $7$,因为跨度超过了 $K$。 ### 数据范围 $2 \le N \le 5000$,$1 \le K \le N − 1$,$0\le H_i \le 10^9$。