Задача №111888. Оптимизация посадки
Петр работает в аэропорту Байтландии. Его работа заключается в том, чтобы оптимизировать процесс посадки пассажиров в самолет. Самолеты в Байтландии имеют \(s\) рядов кресел, пронумерованных от \(1\) до \(s\). В каждом ряду находится шесть кресел, пронумерованных от A до F.
В очереди стоят \(n\) пассажиров, которые по одному садятся в самолет. Если \(i\)-тый пассажир сидит в ряду \(r_i\), то неудобство посадки в самолет для него равна количеству пассажиров, которые сели в самолет до него и сидят в рядах с номерами \(1\) ... \(r_i - 1\). Итоговое неудобство посадки в самолет есть сумма неудобств для всех пассажиров. Например, если в очереди стоят десять пассажиров, и их места 6A, 4B, 2E, 5F, 2A, 3F, 1C, 10E, 8B, 5A, то сложности посадки для каждого из них равны 0, 0, 0, 2, 0, 2, 0, 7, 7, 5, соответственно, и суммарное неудобство равна 23.
Для оптимизации процесса, Петр хочет разделить самолет на \(k\) зон. Каждая зона должна быть непрерывным отрезком рядов кресел. Тогда процесс посадки производится в \(k\) фаз. На каждой фазе выбирается одна зона и все пассажиры, места которых находятся в этой зоне садятся в том порядке, в котором они были в исходной очереди.
В приведенном выше примере, если мы разделим самолет на две зоны: ряды 5-10 и 1-4, то в первой фазе пассажиры займут кресла 6A, 5F, 10E, 8B, 5A, а во второй фазе пассажиры займут места 4B, 2E, 2A, 3F, 1C. Итоговое неудобство будет равно \(6\).
Помогите Петру найти такое разбиение самолета на зоны, которое минимизирует итоговое неудобство посадки.
Первая строка содержит три целых числа \(n\) (\(1 \leq n \leq 1000\)), \(s\) (\(1 \leq s \leq 1000\)) и \(k\) (\(1 \leq k \leq 50\), \(k \leq s\)). Следующая строка содержит \(n\) целых чисел \(r_i\) (\(1 \leq r_i \leq s\)).
В каждом ряду сидит не более \(6\) пассажиров.
Выведите одно число – минимально возможное неудобство.
1 ≤ n, s ≤ 100, 1 ≤ k ≤ 50. Решение оценивается в 60 баллов.
Дополнительные ограничения отсутствуют. Решение оценивается в 40 баллов.
10 12 2 6 4 2 5 2 3 1 11 8 5
6
10 8 2 5 8 1 1 5 3 7 8 8 8
7