Числа - 3

Дана последовательность чисел a₁, a₂, …, a_N. За одну операцию разрешается удалить любое (кроме крайних) число, заплатив за это штраф, равный произведению этого числа на сумму соседних. Требуется удалить все числа, кроме крайних, с минимальным суммарным штрафом.

Например:

• Начальная последовательность: 1 50 51 50 1.
• Удаляем четвёртое число, штраф 50(51+1)=2600, получаем 1 50 51 1.
• Удаляем третье число, штраф 51(50+1)=2601, получаем 1 50 1.
• Удаляем второе число, штраф 50(1+1)=100.
• Итого штраф 5301.

Входные данные

В первой строке входного файла INPUT.TXT записано одно число N (1 ≤ N ≤ 100) - количество чисел в последовательности.

Во второй строке находятся N целых чисел a₁, a₂, …, a_N; никакое из чисел не превосходит по модулю 100.

Выходные данные

В единственную строку выходного файла OUTPUT.TXT нужно вывести одно число - минимальный суммарный штраф.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки] [Решение]