最优二分检索树
说明
给出 $n$ 个数据 $a_1 \le a_2 \le a_3 \le \cdots \le a_n$，第 $i$ 个点有一个权值 $f_i$。
用这 $n$ 个数据构建一个二分检索树。二分检索树是一颗二叉树，任意节点满足所有左边子节点关键字小于等于当前节点，所有右子节点关键字大于等于当前节点。
构建这颗树的代价为所有节点的权值 $f_i$ 乘上深度 $d_i$ 的和。即 $\sum_{i=1}^{n}f_i\cdot d_i$。根节点深度为 $1$。请你计算构建树的最小代价是多少。
输入格式
输入第一行一个整数 $n(1 \le n \le 2000)$。
接下里一行输入 $f_i(1 \le f_i \le 100)$。
输出格式
输出构建树的最小的代价。
样例
5
3 2 2 5 228相关
在下列比赛中: