Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Числа - 3

(Время: 1 сек. Память: 16 Мб Сложность: 58%)

Дана последовательность чисел 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.TXTOUTPUT.TXT
15
1 50 51 50 1
5301

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

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

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483