Подразделы

Другие разделы

Дата и время

09/04/2025 08:10:08

Авторизация

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

And Then There Was One Broken Sword: потерянный файл Decoding Morse Sequences SMS Бросание кубика Витрина Возрастающая подпоследовательность Гангстеры Головоломка умножения Зоопарк Копилка Кубический метр Маршрут Палиндром Разложение на простые слагаемые Скобки (3) Скобки (4) Сообщение Строки Фибоначчи

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

Ограничения: время – 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

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

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