АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

12. Быстрое питание

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Фастфуд-сеть McBurger включает n ресторанов, расположенных вдоль автострады. Недавно владельцы решили построить k складов (k ≤ n), каждый из которых будет размещаться на базе одного из ресторанов (в том же здании, что и ресторан).

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

Требуется написать программу, которая определит оптимальное расположение складов. Критерий оптимальности: сумма расстояний от каждого ресторана до ближайшего к нему склада должна быть наименьшей.

Входные данные

Во входных данных содержится описание нескольких фастфуд-сетей.

Каждое описание начинается со строки, содержащей два целых числа n и k, где n – число ресторанов, k – число складов (1 ≤ n ≤ 200, 1 ≤ k ≤ n). Затем идут n строк, содержащих по одному целому числу – позиции di ресторанов от начала автострады в порядке возрастания. Все позиции лежат в диапазоне от -100000 до 100000.

Входные данные заканчивается, когда n = k = 0.

Выходные данные

Для каждой фастфуд-сети выведите одно целое число – минимально возможную сумму расстояний от каждого ресторана до ближайшего к нему склада.

Пример

Входные данные
6 3
5
6
12
19
20
27
0 0
Выходные данные
8


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи по темам / Динамическое прогр-е, рекуррентные соотношения /
873. Tower of Hanoi 12. 1717. Возрастающая подпоследовательность 67. Восстановление скобок 14. Выражение
Задачи с соревнований / Тренировки ВоГУ / ВоГТУ и ВоГПУ 17.11.2007 /
479. E - Sorting Slides 12. 480. G - Prime Cuts 481. H - Uniform Generator
Задачи с соревнований / Школьные олимпиады Вологодской области / Импульс, смена 2019 / Динамическое программирование /
2. 11 - Дерево поиска 12. 291. 13 - Триангуляция
Задачи с соревнований / Школьные олимпиады Вологодской области / Импульс, сентябрь 2020 / Импульс-2020, ДП /
870. 08 - Куча камней - 2 12.
 
время генерации 0.328 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.