Числа - 3

Задача решается методом динамического программирования.

Заведём квадратную матрицу M размера N*N. В ячейке M_i,j будем хранить минимальный штраф за удаление всех чисел i-го по j-е не включительно (элементы матрицы, у которых i ≥ j, нам не будут нужны). Подсчитывать эти штрафы будем следующим образом: поскольку среди чисел между i-м и j-м какое-то (k-е) мы должны удалить последним, то переберём все k от i до j не включительно и посчитаем наименьший штраф за удаление всех чисел между i и j при условии, что k-е удаляется последним. Этот штраф равен сумме наименьших штрафов за удаление всех чисел c i по k (M_i,k), с k по j (M_k,j) и штрафа за последнее удаление - (a_i+a_j)∙a_k. Тогда очевидно, что:

M_i,j = min _i≤k≤j (M_i,k + M_k,j + (a_i + a_j)∙a_k).

Несложно посчитать элементы матрицы с индексами, отличающимися на 1: так как удалять между соседними числами нечего, то M_i,i+1 = 0.

Осталось только вычислить все элементы матрицы (например, в порядке увеличения разности между индексами) и посмотреть на число M_1,N, которое и будет ответом на задачу.

Кроме того, надо аккуратно обработать случай N=1. Вышеприведённый алгоритм для этого случая не подходит, но очевидно, что, так как удалять при N=1 нечего, то ответ здесь - 0.

[Обсуждение] [Все попытки] [Задача]