Optimal Search Tree
Keys 1..N have access frequencies f1..N. In a binary search tree the cost of a key is (its depth + 1)×its frequency. Print the minimum total access cost over all valid BSTs.
Input: the first line has N; the second line has the N frequencies (in key order).
Output: the minimum weighted access cost.
Constraints:
- 1 ≤ N ≤ 500
- 1 ≤ fi ≤ 100
Sample Tests
Input 1
3 34 8 50
Output 1
92
Input 2
1 5
Output 2
0
Discussion (opens after you solve — no spoilers before)
No comments yet.