НачалоПодразделы
Другие разделы
Дата и время
16/11/2024 23:23:09
Занятие 9
C. Головоломка умножения
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 03/07/2006 | Лето 2006 дорешивание ( 9C) |
| 24/07/2006 | Лето 2006 - 9 (нет результатов) (C) |
| 07/11/2007 | Занятие 9 (C) |
| 09/12/2010 | Сборы: Общий итог (6F) |
| 13/01/2011 | Сборы 6: Домашнее задание (D) |
| 18/02/2013 | Занятие 17 (A) |
| 12/07/2023 | Лето 2023-8 сложные (C) |
| 21/03/2024 | ДП + Игры 1 (проводит BOGAT) (B) |
| 10/07/2024 | Лето 2024-8 сложные (C) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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
