AT_atc002_c 最適二分探索木
题目描述
# 题描述
### 我想制作一个有 n叶的有序二叉树。该二叉树的成本定义如下。
------------
### 然而,depth(i),从在该二进制树的左表示第i片叶子的深度。W_i重量是作为输入给出的。请找到最低成本。
输入格式
### 输入由标准输入以下列形式给出：
```
n n n
w1 w_1 w1 w2 w_2 w2 ... wn w_n wn
```
在第一行中，表示元素数量的整数 n （1≦n≦100,000 )
第二行显示元素的重量给出了 n个整数。 其中i(1≦i≦n) 表示第i个元素的权重 w_i（1≦w_i≦1,000)
输出格式
### 输出由标准输出一下格式给出：
输出满足条件的有序二叉树的最低成本。
### 输入输出样例
暂无测试点
说明/提示
### 部分测试点
```
n ≦ 1 0 0 如果你回答的数据集满意， 50分给出。
n ≦ 3,000 n ≦ 3，0 0 0 如果您在回答数据集令人满意的，除了50分中给出。
如果在没有其他约束的情况下更正数据集，则与上述分开 有一点是给出。
```
# 输入样例
```
6
1 2 3 4 9 3
```
# 输出样例
```
53
```
### 下图中显示的二叉树是最佳的。
### 等效于样本输入和输出的二叉树
### 如果你制作这样的二叉树，那么成本是53。