最优二分检索树
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
给出 $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 22820221003秋季Level-6集训
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 4
- 开始于
- 2022-10-3 18:00
- 结束于
- 2022-10-13 18:00
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 15
