Республиканская олимпиада по информатике. 2018 год
Задача F. Тренерский выбор Тимы
Ограничение по времени:
4 секунды
Ограничение по памяти:
256 мегабайт
Тима с недавних пор начал тренировать баскетбольные команды. Капитаном команды всегда выбирается игрок с максимальным ростом. Также он придумал свою формулу несовместимости игроков в одной команде. Формула зависит от роста всех игроков в команде. Несовместимость игроков в одной команде равняется сумме разниц роста между всеми игроками и ростом капитана. Более формально, пусть $h_1, h_2, ... , h_m$ это рост игроков команды, $mx = max(h_1, h_2, ..., h_m)$, тогда несовместимость = $\sum_{i=1}^{m} mx$-$h_i$. У Тимы есть $n$ игроков выстроенных в ряд, $i$-й из них имеет рост $a_i$. Он хочет разбить всех на $k$ команд, каждый игрок должен быть в ровно одной команде и команда должна состоять из игроков, которые составляют непрерывный отрезок в ряду. Тима хочет собрать команды так, чтобы суммарная несовместимость была минимальной. Помогите Тиме разбить на команды оптимально.
Формат входного файла
Первая строка входных данных содержит два целых чисел $n$ и $k$ ($1 \le n \le 10^5$, $1 \le k \le min(n, 20)$) — количество игроков в ряду и количество команд. Вторая строка содержит $n$ целых чисел $a_i$ ($1 \le a_i \le 10^6$) — рост $i$-го игрока слева в ряду в сантиметрах.
Формат выходного файла
Выведите единственное целое число — ответ на задачу.
Система оценки
Данная задача содержит шесть подзадач, в каждой подзадаче выполняются ограничения из условий:
- $n \le 100$, $k = 1$. Оценивается в $5$ баллов.
- $n \le 2000$. Оценивается в $11$ баллов.
- $k = 2$. Оценивается в $8$ баллов.
- $k = 3$. Оценивается в $15$ баллов.
- $a_i \le a_{i+1}$, для всех $1 \le i < n$. Оценивается в $19$ баллов.
- Ограничения из условия задачи. Оценивается в $42$ баллов.
Пример:
Вход 7 3 6 4 1 5 3 2 2Ответ
7Вход
5 2 4 1 5 5 6Ответ
5Вход
9 2 3 7 4 1 3 2 4 6 7Ответ
22( Temirlan Satylkhanov )
Комментарий/решение:
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.