Задача A. Перепад глубины

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:100  

Условие

Автономный необитаемый подводный аппарат проплыл по заданной траектории, записав последовательность целых чисел ai — глубину своего погружения в метрах на i-й секунде.

Известно, что за одну секунду глубина погружения не может измениться более чем на d метров в большую или меньшую сторону. Определение глубины не всегда работает точно, из-за чего это условие может быть нарушено в исходной последовательности. Необходимо очистить данные, удалив из них как можно меньше элементов.

Требуется написать программу, которая по данным ai и d определит наименьшее возможное количество элементов, которые нужно удалить из последовательности ai чтобы разность рядом стоящих элементов в оставшейся последовательности по модулю не превосходила d.

Формат входных данных

Входные данные содержат целые числа n и d — количество измерений и максимальный перепад глубины. Далее следует n целых чисел ai — измерения глубины.

Формат выходных данных

Выходные данные должны содержать единственное целое число — наименьшее количество удаляемых элементов.

Ограничения

1 ≤ n ≤ 20 000, 0 ≤ d ≤ 1000, 0 ≤ ai ≤ 109

Примеры тестов

Стандартный вход Стандартный выход
1
3 4
10 15 14
1

Разбор

Задача решается методом динамического программирования.

Пусть dpi — минимальное количество элементов, которые нужно удалить, чтобы элементы на префиксе с 1-го по i-й имели перепад не более d, и при этом элемент i остался в последовательности.

Тогда dp1 = 0 и dpi = minj = 1,i − 1dpj + i − j − 1, i = 2,n.

Следует также учесть возможность удаления элементов в суффиксе последовательности, поэтому окончательный ответ равен mini = 1,ndpi + n − i.


0.103s 0.013s 13