Optimal Binary Search Tree#1522
Given a set S = \{e_1, e_2, \ldots, e_n\} of distinct elements such that e_1 < e_2 < \ldots < e_n, consider a binary search tree of the elements of . The higher the query frequency of an element, the closer it should be to the root.
The cost of accessing an element e_i of in the tree, denoted cost(e_i), is equal to the number of edges in the path connecting the root to the node containing e_i. Given the query frequencies of the elements of , f(e_1), f(e_2), \ldots, f(e_n), the total cost of the tree is defined as:
The tree with the lowest total cost is considered the best for searching elements of . Such a tree is called the Optimal Binary Search Tree.
The input contains several test cases, each on a separate line. The first number on each line, (1 \leq n \leq 250), is the size of . The next non-negative integers on the same line are the query frequencies of the elements of : f(e_1), f(e_2), \ldots, f(e_n) (0 \leq f(e_i) \leq 100).
For each test case, print the total cost of the Optimal Binary Search Tree on a separate line.
Example 1