Задачі
Оптимальне бінарне дерево пошуку
Оптимальне бінарне дерево пошуку
Розглянемо множину $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$. Тому воно називається Оптимальним Бінарним Деревом Пошуку.
\InputFile
Складається з декількох тестів, кожний з яких розташований в окремому рядку. Перше число в рядку $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)$.
\OutputFile
Для кожного тесту в окремому рядку вивести вартість Оптимального Бінарного Дерева Пошуку.
Вхідні дані #1
1 5 3 3 1 7 7 4 10 6 2 3 5 7 6 1 3 5 10 20 30
Вихідні дані #1
0 5 49 63