問題
Colorado의 농부 Ron은 그의 소들을 위해 스키 리조트를 짓고 있다.
(하지만 예산의 제한으로 오직 1개의 스키 리프트만 짓기로 했다).
스키 리프트는 모노레일 형식으로 지어질 것이고,
몇몇 개의 중간 지지물들(각각의 높이는 땅에 대해 0이상 높은)에 의해서
출발 지점의 콘크리트로 만든 지지물과 도착지점을 연결하게 될 것이다.
직선으로 된 철근 조각들은 모든 인접한 지지물 쌍들을 연결하게 된다.
당연히, 각각의 곧은 철근 조각들은 모든 지점에서 땅보다 높게 놓여야 한다.
언제나 근검하는 농부 Ron은 그가 반드시 지어야 하는 지지물들의 수를 최소화 하고 싶다.
그는 리프트가 지나게 될 같은 크기의 지점들 N(2 ≤ N ≤ 5,000)곳을 조사해서
각각 지점들의 총체적인 높이들 H(0 ≤ H ≤ 1,000,000,000)를 기록해 두었다.
안전 수칙들은 농부 Ron이 인접한 지지물들을 K(1≤ K≤ N-1) 단위 거리 이하로 연결 되도록 제한한다.
한 쌍의 인접한 지지물들을 연결해주는 철근은 완고하게 제작되었고 한 지지물로부터 다음 지지물을 직선을 그리며 이어주게 된다.
농부 Ron을 도와서 다음 조건들을 만족하면서 가장 적은 수의 지지물들을 짓도록 해주자.
철근 각각은 전체적으로 땅보다 위에(혹은 오직 접해 있거나) 있어야 하고,
어떤 두개의 연속한 지지물도 K개보다 많은 단위만큼 수평적으로 떨어지면 안되고, 땅의 처음과 마지막 지점에는 지지물을 건설해야 한다.
入力
1번째 줄: 공백으로 구분된 두 개의 정수 N과 K 2번째 줄...N+1 번째 줄: i+1번째 줄은 i번째 지점의 높이를 나타내는 단 1개의 정수로 구성됨
出力
가장 적은 리프트 타워(지지물)의 수를 나타내는 단 한 개의 정수를 출력한다. 농부 Ron은 위의 제한들을 만족하면서 건설해야 한다
例題
13 4
0
1
0
2
4
6
8
6
8
8
9
11
12
5
ログインしないとコードを書けません。