Головоломка умножения
(Время: 1 сек. Память: 16 Мб Сложность: 47%)
В головоломку умножения играют с рядом карт, каждая из которых содержит одно положительное целое число. Во время хода игрок убирает одну карту из ряда и получает число очков, равное произведению числа на убранной карте и чисел на картах, лежащих непосредственно слева и справа от неё. Не разрешено убирать первую и последнюю карты ряда. После последнего хода в ряду остаётся только две карты.
Цель игры – убрать карты в таком порядке, чтобы минимизировать общее количество набранных очков.
Например, если карты содержат числа 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.
Входные данные
В первой строке входного файла INPUT.TXT находится число карт N (3 ≤ N ≤ 100), во второй – разделённые пробелами N чисел на картах (целые числа в диапазоне от 1 до 100).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число – минимально возможное число очков.
Пример
№ | INPUT.TXT | OUTPUT.TXT |
1 | 6 10 1 50 50 20 5 | 3650 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|