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

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

HotLog

Объединение блоков

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

Изделие изготавливают из n блоков, каждый из которых имеет два технологических параметра – mi и ki. Известно, что ki=mi+1, i=1, 2, …, n-1. При этом условии два последовательных блока i и i+1 можно объединять в один новый, который будет иметь технологические параметры - mi и ki+1, и на это потребуется mi*ki+1 технологических операций. Новый блок можно опять объединять с одним из соседних и так далее. Меняя порядок сборки блоков можно добиться уменьшения количества технологических операций.

Поясним это на примере трех блоков: 34 и 29, 29 и 4, 4 и 15. Если собрать вначале 2 и 3 блок, а затем присоединить собранное к первому, то потребуется 29*15+34*15=435+510=945 операций. Если собрать вначале блок из 1 и 2 исходных блоков, а затем присоединить 3 блок, то потребуется 34*4+34*15=136+510=646 операций.

Требуется написать программу, которая найдет минимальное число технологических операций для изготовления изделия.

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

Входной файл INPUT.TXT содержит в первой строке число n – количество блоков (1 ≤ n ≤ 100). Последующие n строк содержат пары чисел (разделенных пробелом) – технологические параметры блоков. Технологические параметры – целые неотрицательные числа, не превышающие 100.

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

Выходной текстовый файл OUTPUT.TXT должен содержать одно число – минимальное число технологических операций.

Пример

INPUT.TXTOUTPUT.TXT
13
34 29
29 4
4 15
646

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

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

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