Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

Числа - 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.TXTOUTPUT.TXT
15
1 50 51 50 1
5301

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

[Все попытки] [Лучшие попытки]

 
     
Югорский НИИ ИТ, Югорский ФМЛ