|
Числа - 3
(Время: 1 сек. Память: 16 Мб Сложность: 48%)
Дана последовательность чисел a1, a2, …, aN. За одну операцию разрешается удалить любое (кроме крайних) число, заплатив за это штраф, равный произведению этого числа на сумму соседних. Требуется удалить все числа, кроме крайних, с минимальным суммарным штрафом.
Например:
- Начальная последовательность: 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 целых чисел a1, a2, …, aN; никакое из чисел не превосходит по модулю 100.
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести одно число - минимальный суммарный штраф.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5
1 50 51 50 1 | 5301 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
