← 返回题目列表

AtCoder · atc002_c

C. 最适用二分探索木

中文机器翻译题面 查看原题

問題文

n 想要创建一个拥有个叶子的有序二叉树。 这个二叉树的成本定义如下。

Σ_{i=1}^{n} w_i × depth(i)

但是,depth(i) 表示在二叉树中从左开始 i 第一个叶子的深度。 w_i 是作为输入给出的权重。 求成本的最小值。


入力

输入是按以下格式从标准输入给出的。

n
w_1 w_2 ... w_n
  • 1 行表示元素的个数的整数 n (1≦n≦100,000) 。
  • 2 行表示元素的权重 n 个整数被给出。在这些中 i (1≦i≦n) 第个元素表示,i 第个元素的权重。 w_i(1≦w_i≦1,000) 。

出力

输出满足条件的有序二叉树的最小成本值。


部分点

针对此问题设置了部分分数。

  • n ≦ 100 如果数据集满足条件并且答案正确,50 点。 如果您对除上述数据集之外的所有满足
  • n ≦ 3,000 如果数据集满足条件并且答案正确,与上述不同 50 点。 如果您对除上述数据集之外的所有满足
  • 如果正确回答了附加的无否定数据集,与上述不同 1 点。 如果您对除上述数据集之外的所有满足

解説


入力例1

6
1 2 3 4 9 3

出力例1

53

以下图所示的二叉树是最适合的。

图1:与示例输入输出相对应的二叉树

如果构造了这样的二叉树,成本为53。