luogu#P4909. [USACO06MAR] Ski Lift G

[USACO06MAR] Ski Lift G

题目描述

科罗拉多州的山脉是二维平面上的一条折线。这条折线由 NN 个端点,N1N−1 段线段组成,第 ii 个端点的横坐标就是 ii,纵坐标是 HiH_i,纵坐标代表高度,也可以称为海拔。

罗恩打算为奶牛建造一个滑雪场,为此要在山脉上规划一条缆车线路。缆线也是一条折线,由若干段缆绳组成,起点在山脉的第一个端点,终点在最后一个端点。每段缆绳可以贴着山脉的轮廓,也可以悬浮于空中,跳过山脉上几个海拔低的端点。每段缆绳的水平跨度有限制,不能超过给定的整数 KK。罗恩需要在每段缆绳的端点处修建支柱,用来固定缆绳。

请帮助他规划一下,选择在山脉的哪些端点上修建,才能使得支柱数量最少?注意,根据题意,起点和终点上是一定要修建的。

输入格式

第一行:两个整数 NNKK

第二行到第 N+1N + 1 行,第 i+1i+1 行有一个整数 HiH_i

输出格式

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

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

提示

解释 最优方案是把支柱设在 1,5,7,9,131,5,7,9,1355 不能直接连 99,因为 99 的海拔较高,11 不能直接连 77,因为跨度超过了 KK

数据范围

2N50002 \le N \le 50001KN11 \le K \le N − 10Hi1090\le H_i \le 10^9