printЗанятие 9

printC. Головоломка умножения

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В головоломку умножения играют с рядом карт, каждая из которых содержит одно положительное целое число. Во время хода игрок убирает одну карту из ряда и получает число очков, равное произведению числа на убранной карте и чисел на картах, лежащих непосредственно слева и справа от неё. Не разрешено убирать первую и последнюю карты ряда. После последнего хода в ряду остаётся только две карты.
Цель игры – убрать карты в таком порядке, чтобы минимизировать общее количество набранных очков.
Например, если карты содержат числа 10, 1, 50, 20 и 5, игрок может взять карту с числом 1, затем 20 и 50, получая очки
`10⋅1⋅50\ +\ 50⋅20⋅5\ +\ 10⋅50⋅5\ =\ 500\ +\ 5000\ +\ 2500\ =\ 8000`.
Если бы он взял карты в обратном порядке, то есть 50, затем 20, затем 1, количество очков было бы таким:
`1⋅50⋅20\ +\ 1⋅20⋅5\ +\ 10⋅1⋅5\ =\ 1000\ +\ 100\ +\ 50\ =\ 1150`.
Ввод
В первой строке находится число карт `N` (`3\ ≤\ N\ ≤\ 100`), во второй – разделённые пробелами `N` чисел на картах. Числа на картах целые от 1 до 100.
Вывод
Вывести одно целое число – минимально возможное число очков.

Пример ввода

6
10 1 50 50 20 5

Пример вывода

3650
Источник: Far-Eastern quarterfinal NEERC, 2001
loading