e-olymp
Соревнования

February 21 - March 3. Dynamic Programming

Оптимальное бинарное дерево поиска

Рассмотрим множество S = {e1, e2, ..., en}, состоящее из n различных элементов таких, что e1 < e2 < ... < en. Рассмотрим бинарное дерево поиска, состоящее из элементов S. Чем чаще производится запрос к элементу, тем ближе он должен располагаться к корню.

Стоимостью cost доступа к элементу ei из S в дереве будем называть значение cost(ei), равное числу ребер на пути, который соединяет корень с вершиной, содержащей элемент. Имея частоту запросов к элементам из S, (f(e1), f(e2), ..., f(en)), определим общую стоимость дерева следующим образом:

f(e1) · cost(e1) + f(e2) · cost(e2) + ... + f(en) · cost(en)

Дерево, имеющее наименьшую стоимость, считается наилучшим для поиска элементов из S. Именно поэтому оно называется Оптимальным Бинарным Деревом Поиска.

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

Состоит из нескольких тестов, каждый из которых расположен в отдельной строке. Первое число в строке n (1n250) указывает на размер множества S. Следующие n неотрицательных целых чисел описывают частоты запросов элементов из S: f(e1), f(e2), ..., f(en). Известно, что 0f(ei) ≤ 100.

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

Для каждого теста в отдельной строке вывести стоимость Оптимального Бинарного Дерева Поиска.

Лимит времени 2 секунды
Лимит использования памяти 64 MiB
Входные данные #1
1 5
3 10 10 10
3 5 10 20
6 1 3 5 10 20 30
Выходные данные #1
0
20
20
63