Трюк с открытым и закрытым интервалом

Трюк с открытым и закрытым интервалом

Введение

В некоторых задачах ДП нам нужно строить группы (или интервалы), где итоговое значение зависит от первого и последнего элемента каждой группы. Очень полезный шаблон для этого — Трюк открытия и закрытия интервала.

Идея проста:

• Мы обрабатываем элементы в отсортированном порядке.
• Мы позволяем группам временно быть открытыми.
• Позже мы закрываем их, когда фиксируется их правый конец.

Это позволяет избежать явного отслеживания всех концов интервалов.

Условие задачи

Нам даны $n$ программистов с уровнями навыка от $0$ до $100$. Мы хотим разделить их на команды так, чтобы суммарный штраф был не больше $x$.

Для команды штраф = разность между максимальным и минимальным навыком.

Суммарный штраф = сумма штрафов всех команд.

Посчитайте количество корректных способов сформировать команды.

Ключевая идея

Отсортируем программистов по навыку.
Теперь каждая команда становится непрерывным отрезком в отсортированном порядке.

При просмотре программистов слева направо:

• некоторые команды уже завершены
• некоторые команды всё ещё открыты (мы выбрали минимум, но ещё не максимум)

Поэтому ДП отслеживает, сколько команд сейчас открыто.