2136: 最小代价二叉树

一棵二叉树的代价是指，该二叉树每个结点的权值与该结点所在高度的乘积之和。

设一棵二叉树的中根遍历为1,2,...,i,...,n，各个点的权值分别为c1,c2,...,ci,...,cn，高度为h1,h2,...,hn，则这棵二叉树的代价为Σ(ci*hi)。

例如，一棵树的结点数为4，中根遍历下的权值为4,1,2,3，则下图为一种合法情况，这棵二叉树的代价为19。可以证明，这种构造二叉树的方法所产生的代价是最小的。

现在，给你n个结点的权值，请求出这棵二叉树的一种构造方法，使其代价最小。简单起见，只要输出最小代价即可，不需输出构造方法。

第一行为一个整数n(n∈N*且n<=2500)，表示结点总数。

接下来的n行，第i行只有一个整数ci(ci∈N*且ci<=16)，含义如描述所述。

只有一个整数，代表二叉树的最小代价。

4
4
1
2
3

19