For the grand finale, Dip wants to build an optimal decision tree over frequently-asked puzzle categories, minimizing the average number of questions asked to find any category. Given N keys with access frequencies, build a binary search tree over them (keys must stay in sorted order as a BST) to MINIMIZE the total weighted search cost (sum of frequency × depth, root at depth 1). Print the minimum cost using interval DP.
Input
Line1: N. Line2: N frequencies (corresponding to keys already given in sorted order).
Output
Minimum weighted search cost.
Constraints
1 ≤ N ≤ 500
Sample Input
3 34 8 50
Sample Output
142
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.