eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Рассмотрим множество 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)), определим общую стоимость дерева следующим образом:

f(e_1) \cdot cost(e_1) + f(e_2) \cdot cost(e_2) + ... + f(e_n) \cdot cost(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ə

Giriş verilənləri #1
1 5
3 3 1 7
7 4 10 6 2 3 5 7
6 1 3 5 10 20 30
Çıxış verilənləri #1
0
5
49
63