Оптимальное бинарное дерево поиска
Оптимальное бинарное дерево поиска
Рассмотрим множество S = \{e_1, e_2, ..., e_n\}, состоящее из n различных элементов таких, что e_1 < e_2 < ... < e_n. Рассмотрим бинарное дерево поиска, состоящее из элементов S. Чем чаще производится запрос к элементу, тем ближе он должен располагаться к корню.
Стоимостью cost доступа к элементу e_i из S в дереве будем называть значение cost(e_i), равное числу ребер на пути, который соединяет корень с вершиной, содержащей элемент. Имея частоту запросов к элементам из S, (f(e_1), f(e_2), ..., f(e_n)), определим общую стоимость дерева следующим образом:
Дерево, имеющее наименьшую стоимость, считается наилучшим для поиска элементов из S. Именно поэтому оно называется Оптимальным Бинарным Деревом Поиска.
Giriş verilənləri
Состоит из нескольких тестов, каждый из которых расположен в отдельной строке. Первое число в строке n~(1 \le n \le 250) указывает на размер множества S. Следующие n неотрицательных целых чисел описывают частоты запросов элементов из S: f(e_1), f(e_2), ..., f(e_n)~(0 \le f(e_i) \le 100).
Çıxış verilənləri
Для каждого теста в отдельной строке вывести стоимость Оптимального Бинарного Дерева Поиска.
Nümunə
1 5 3 3 1 7 7 4 10 6 2 3 5 7 6 1 3 5 10 20 30
0 5 49 63