Модуль: Паттерны в динамическом программировании


Задача

3 /7


Сумма минимумов

Теория Нажмите, чтобы прочитать/скрыть


Если необходимо разделить массив на ровно k подотрезков, то просто добавляется второй параметр в динамическом программировании - на сколько отрезков разбиваем.
То есть теперь будем считать следующее дп:
dp[i][j] - ответ для первых i элементов, если мы разбиваем их на ровно j отрезков.
Следите за невалидными состояниями.

Пересчет динамики такой же, но с учетом второго параметра. То есть подсчитывая dp[i][k] и перебирая левую границу последнего подотрезка j, то пересчитываем dp[i][k] через dp[j - 1][k - 1] и значение отрезка [j;i].

Задача

Вам дан массив из n целых чисел. Вам необходимо разделить его на k непустых подотрезков (последовательность подряд идущих элементов) так, чтобы:
1) Каждый элемент массива входил ровно в один подотрезок.
2) Если для каждого подотрезка выбрать минимальное в нем число, то сумма всех минимумов должна быть максимально возможной.

Сообщите сумму минимумов значений в подотрезках этого разбиения.

Входные данные:
В первой строке дается два натуральных числа - n (1 <= n <= 500) и k (1 <= k <= n).
Во второй строке дается n целых чисел - элементы массива ai (1 <= ai <= 105).

Выходные данные:
Выведите одно число - ответ на задачу.

Пример:
 
Входные данные Выходные данные
5 3
4 2 5 1 3
8

Пояснение:
Одно из подходящих разбиений: [4, 2], [5], [1, 3]. Сумма минимумов в каждом подотрезке равна 2 + 5 + 1 = 8.

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w643
Комментарий учителя