Задача №111792. Головоломка умножения
В головоломку умножения играют с рядом карт, каждая из которых содержит одно положительное целое число. Во время хода игрок убирает одну карту из ряда и получает число очков, равное произведению числа на убранной карте и чисел на картах, лежащих непосредственно слева и справа от неё. Не разрешено убирать первую и последнюю карты ряда. После последнего хода в ряду остаются только эти две карты.
Цель игры — убрать карты в таком порядке, чтобы минимизировать общее количество набранных очков.
Например, если карты содержат числа 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, во второй — разделённые пробелами N чисел на картах. Ограничения: 3 ≤ N ≤ 100, числа на картах целые от 1 до 100.
Вывести одно целое число — минимально возможное число очков.
6 10 1 50 50 20 5
3650