填空题
最优二叉树
发布于 2022-03-03 16:16:06
小美有一个由N个点组成的二叉树，每个点有一个权值。定义二叉树每个点的开销为其权值与深度的乘积（每个点的深度为其到根节点的距离，即其到根节点的路径上的边数），二叉树的总开销即每个点的开销之和。小美按照二叉树的中序遍历依次记录下每个点的权值，即她记录下了N个数，第i个数表示位于中序遍历第i个位置的点的权值。之后由于某种原因，小美遗忘了二叉树的具体结构。在所有可能的二叉树中，总开销最小的二叉树被称为最优二叉树。现在，小美请小团求出最优二叉树的总开销。
输入描述：第一行输入一个整数N（1<=N<=300），表示二叉树的点数。
第二行输入N个由空格隔开的整数，表示按中序遍历记录下的各个点的权值，所有权值均为不超过10^4的正整数。
输入样例： 5 7 6 5 1 3 输出描述：输出一个整数，表示最优二叉树的总开销。
输出样例 21关注者
0
被浏览
11
