Оптимальне бінарне дерево пошуку
Оптимальне бінарне дерево пошуку
Розглянемо множину 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. Тому воно називається Оптимальним Бінарним Деревом Пошуку.
Вхідні дані
Складається з декількох тестів, кожний з яких розташований в окремому рядку. Перше число в рядку 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).
Вихідні дані
Для кожного тесту в окремому рядку вивести вартість Оптимального Бінарного Дерева Пошуку.
Приклад
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