/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君は市役所の道路管理担当者です。担当する通りには N 枚の舗装ブロックが一列に並んでおり、各ブロックには左から順に 1 から N までの番号が付けられています。
長年の使用により、各ブロック i の地面からの高さは整数値 D_i となっています。隣り合う 2 つのブロック i と i+1 について、高さの差の絶対値が閾値 T を超えている、すなわち |D_i - D_{i+1}| > T である箇所では、歩行者がつまずく危険な段差が生じています。このような隣り合うブロックの組 (i, i+1)（1 \leq i \leq N-1）を「危険箇所」と呼びます。
高橋君は、危険箇所を減らすために、N 枚のブロックの中から最大 K 枚の異なるブロックを選んで新しいものに交換し、それぞれの高さを好きな整数値に設定し直すことができます（0 枚、すなわち何も交換しないことも可能です）。設定する高さに上限・下限はありません。交換するブロックとそれぞれの高さを適切に決めることで、危険箇所の数を最小化したいと考えています。
最適にブロックの交換を行ったとき、危険箇所の数の最小値を求めてください。
制約
- 2 \leq N \leq 10
- 1 \leq T \leq 100
- 0 \leq K \leq N
- 0 \leq D_i \leq 100 (1 \leq i \leq N)
- 入力はすべて整数である
入力
N T K D_1 D_2 \ldots D_N
- 1 行目には、ブロックの枚数を表す整数 N 、閾値を表す整数 T 、交換できるブロックの最大枚数を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各ブロックの高さを表す整数 D_1, D_2, \ldots, D_N が、スペース区切りで与えられる。
出力
最適にブロックの交換を行ったときの危険箇所の数の最小値を 1 行で出力せよ。
入力例 1
4 2 1 1 5 6 10
出力例 1
1
入力例 2
5 3 0 1 10 11 20 21
出力例 2
2
入力例 3
7 5 2 0 20 21 22 50 51 0
出力例 3
1
入力例 4
10 10 3 0 30 60 55 56 100 10 20 90 91
出力例 4
2
入力例 5
2 100 0 0 100
出力例 5
0
Score : 366 pts
Problem Statement
Takahashi is a road maintenance officer at the city hall. The street he is responsible for has N paving blocks lined up in a row, and each block is numbered from 1 to N from left to right.
Due to years of use, the height of each block i from the ground has become an integer value D_i. For two adjacent blocks i and i+1, if the absolute difference in height exceeds the threshold T, that is, |D_i - D_{i+1}| > T, a dangerous step that may cause pedestrians to trip has formed. Such a pair of adjacent blocks (i, i+1) (1 \leq i \leq N-1) is called a "hazardous spot".
To reduce the number of hazardous spots, Takahashi can select at most K distinct blocks from the N blocks, replace them with new ones, and set each of their heights to any integer value he likes (choosing 0 blocks, i.e., replacing nothing, is also allowed). There is no upper or lower limit on the heights that can be set. He wants to minimize the number of hazardous spots by appropriately choosing which blocks to replace and what height to set each of them to.
Find the minimum number of hazardous spots when the block replacement is performed optimally.
Constraints
- 2 \leq N \leq 10
- 1 \leq T \leq 100
- 0 \leq K \leq N
- 0 \leq D_i \leq 100 (1 \leq i \leq N)
- All input values are integers
Input
N T K D_1 D_2 \ldots D_N
- The first line contains an integer N representing the number of blocks, an integer T representing the threshold, and an integer K representing the maximum number of blocks that can be replaced, separated by spaces.
- The second line contains integers D_1, D_2, \ldots, D_N representing the height of each block, separated by spaces.
Output
Output in one line the minimum number of hazardous spots when the block replacement is performed optimally.
Sample Input 1
4 2 1 1 5 6 10
Sample Output 1
1
Sample Input 2
5 3 0 1 10 11 20 21
Sample Output 2
2
Sample Input 3
7 5 2 0 20 21 22 50 51 0
Sample Output 3
1
Sample Input 4
10 10 3 0 30 60 55 56 100 10 20 90 91
Sample Output 4
2
Sample Input 5
2 100 0 0 100
Sample Output 5
0