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

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

HotLog


 

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

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

Изделие изготавливают из 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

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

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

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