Задача №111817. Abcdefg (ещё бОльшие ограничения --- T)
(Задача отличается от предыдущых исключительно ограничениями.)
Есть сообщение, записанное в алфавите из N символов. Известно, что 1-й, 2-й, ..., N -й символы алфавита использованы в сообщении f 1 , f 2 , ..., f N раз. Его необходимо набрать на M -клавишной клавиатуре, используя способ набора, аналогичный используемому в мобильных телефонах.
На телефоне, клавише 2 сопоставлены буквы abc, клавише 3 — def, и т.д. Для набора текста телефон переводится в специальный режим, в котором одно нажатие на клавишу 2 порождает символ a, 2 подряд нажатия на 2 символ b, 3 подряд символ c; аналогично, одно нажатие 3 порождает d, 2 подряд e и т. д. Если же необходимо набрать 2 подряд буквы a, то нажимают клавишу 2, немного ждут и снова нажимают клавишу 2.
В нашем случае, символы с 1-ого по некоторый K 1 -ый должны соответствовать 1-ой клавише, с ( K 1 + 1) -ого по некоторый K 2 -ой — 2-ой клавише и т. д., до K M = N . Конкретные значения K 1 , K 2 , ..., K M - 1 не задаются — их, наоборот, нужно подобрать.
Напишите программу, которая будет искать минимальное необходимое количество нажатий на клавиши для набора указанного сообщения на указанной клавиатуре.
В первой строке содержатся два числа N и M , во второй — N чисел f 1 , f 2 , ..., f N — количества вхождений соответствующего символа. Числа внутри строк разделены одинарными пробелами. 2 ≤ M ≤ 1500 , 3 ≤ N ≤ 2000 , M < N , 1 ≤ f i ≤ 1000 .
Необходимо вывести единственное число — найденное минимальное количество нажатий на клавиши.
Значение 21 достигается при K 1 = 2 , K 2 = 3 (1-й и 2-й символы сопоставить 1-й клавише, 3-й символ 2-й клавише, 4-й и 5-й символы 3-й клавише). Тогда количество нажатий будет
(3 × 1 + 2 × 2) + (5 × 1) + (7 × 1 + 1 × 2) = 21 .
5 3 3 2 5 7 1
21