Dynamic programming O(n^3)

Optimal Binary Search Tree

Given a set S = {e1, e2, ..., en} of n distinct elements such that e1 < e2 < ... < en and considering a binary search tree of the elements of S, it is desired that higher the query frequency of an element, closer will it be to the root.

The cost of accessing an element ei of S in a tree cost(ei) is equal to the number of edges in the path that connects the root with the node that contains the element. Given the query frequencies of the elements of S, (f(e1), f(e2), ..., f(en)), we say that the total cost of a tree is the following summation:

f(e1) · cost(e1) + f(e2) · cost(e2) + ... + f(en) · cost(en)

In this manner, the tree with the lowest total cost is the one with the best representation for searching elements of S. Because of this, it is called the Optimal Binary Search Tree.


Contains several instances, one per line. Each line will start with a number n (1n250), indicating the size of S. Following n, in the same line, there will be n non-negative integers representing the query frequencies of the elements of S: f(e1), f(e2), ..., f(en). It is known that 0f(ei) ≤ 100.


For each input instance you must print a line with the total cost of the Optimal Binary Search Tree.

Time limit 2 seconds
Memory limit 128 MiB
Input example #1
1 5
3 3 1 7
7 4 10 6 2 3 5 7
6 1 3 5 10 20 30
Output example #1