11719. Уменьшить массив

Задан массив, состоящий из n целых чисел, и число k. Найдите минимальную стоимость сведения массива до одного элемента. Вы можете выполнять следующую операцию любое количество раз:

· Выберите любую пару соседних элементов a_i и a_i+1 и замените их на (a_i + a_i+1). Стоимость такой операции равна k * (a_i + a_i+1).

Вход. Первая строка содержит два натуральных числа n и k (n, k ≤ 100). Вторая строка содержит n целых чисел a₁, a₂, …, a_n (0 ≤ a_i ≤ 100).

Выход. Выведите минимальную стоимость сведения массива до одного элемента.

Пример входа 1	Пример выхода 1
3 2 1 2 3	18
Пример входа 2	Пример выхода 2
4 3 4 5 6 7	132

РЕШЕНИЕ

динамическое программирование

Анализ алгоритма

Пусть f(i, j) – минимальная стоимость, за которую можно свести массив [a_i, …, a_j] до одного элемента. Это значение будем хранить в ячейке dp[i][j].

Очевидно, что f(i, i) = 0.

Из условия задачи следует, что

f(i, i + 1) = k * (a_i + a_i+1)

Вычислим значение f(i, i + 2). Объединение трех чисел в одно можно совершить двумя способами:

· Объединить a_i и a_i+1 за k * (a_i + a_i+1), после чего объединить a_i + a_i+1 и a_i+2 за k * (a_i + a_i+1 + a_i+2).

· Объединить a_i+1 и a_i+2 за k * (a_i+1 + a_i+2), после чего объединить a_i и a_i+1 + a_i+2 за k * (a_i + a_i+1 + a_i+2).

Таким образом f(i, i + 2) =

min(k * (a_i + a_i+1) + k * (a_i + a_i+1 + a_i+2), k * (a_i+1 + a_i+2) + k * (a_i + a_i+1 + a_i+2))

Теперь рассмотрим вычисление значения f(i, j). Для преобразования массива [a_i, …, a_j] в один элемент, который будет равен a_i + …+ a_j, следует выбрать некоторое значение p (i ≤ p < j), рекурсивно решить задачу для массивов [a_i, …, a_p] и [a_p+1, …, a_j], после чего объединить элементы a_i + … + a_p и a_p+1 + … + a_j. Значение p следует выбрать таким образом, чтобы стоимость преобразования была минимальной:

f(i, j) =

Для быстрых вычислений сумм a_i + …+ a_j воспользуемся массивом префиксных сумм pref, в котором

pref[i] = a₁ + …+ a_i,

откуда a_i + …+ a_j = pref[j] – pref[i – 1] .

Реализация алгоритма

Объявим рабочие массивы.

#define MAX 101

#define INF 0x3F3F3F3F

int dp[MAX][MAX], a[MAX], pref[MAX];

Функция f(i, j) возвращает минимальную стоимость, за которую можно преобразовать массив [a_i, …, a_j] к одному элементу.

int f(int i, int j)

{

if (dp[i][j] == INF)

for (int p = i; p < j; p++)

dp[i][j] = min(dp[i][j], f(i, p) + f(p + 1, j) +

(pref[j] - pref[i - 1]) * k);

return dp[i][j];

}

Основная часть программы. Читаем входные данные.

scanf("%d %d", &n, &k);

memset(dp, 0x3F, sizeof(dp));

for (i = 1; i <= n; i++)

{

scanf("%d", &a[i]);

dp[i][i] = 0;

Вычисляем массив префиксных сумм.

pref[i] = pref[i - 1] + a[i];

}

Вычисляем и выводим ответ.

printf("%d\n", f(1, n));

Python реализация

Объявим константу бесконечность.

INF = float('inf')

Функция f(i, j) возвращает минимальную стоимость, за которую можно преобразовать массив [a_i, …, a_j] к одному элементу.

def f(i, j):

if dp[i][j] == INF:

for p in range(i, j):

dp[i][j] = min(dp[i][j], f(i, p) + f(p + 1, j) +

(pref[j] - pref[i - 1]) * k)

return dp[i][j]

Основная часть программы. Читаем входные данные.

n, k = map(int, input().split())

a = [0] + list(map(int, input().split()))

Вычисляем массив префиксных сумм.

pref = [0] * (n + 1)

for i in range(1, n + 1):

pref[i] = pref[i - 1] + a[i]

Инициализируем массив dp.

dp = [[INF] * (n + 1) for _ in range(n + 1)]

for i in range(1, n + 1):

dp[i][i] = 0

Вычисляем и выводим ответ.

print(f(1, n))