描述
以下我们定义树的基本术语。树的定义是归纳的：它有一个根节点，根节点可以是一个外部节点（叶子），也可以是一个内部节点，内部节点有一系列子树作为其子节点。内部节点也称为其子树根节点的父节点。树中节点的层级是归纳定义的：根节点的层级为$0$，而节点的层级是其父节点层级加$1$。

二叉树的每个内部节点恰好有两个子节点，分别是左子树和右子树。带标签的二叉树的每个内部节点还额外标记有一个字符串作为其标签。二叉搜索树是一种带标签的二叉树，其中每个内部节点$t$满足以下条件：$t$的左子树中所有节点的标签都小于$t$的标签，而$t$的标签又小于其右子树中所有节点的标签。对于这一条件，我们假设字符串是按字典序（即字母顺序）排列的。

树的中序遍历是递归定义的：叶子节点只需被访问，而对于内部节点，首先中序遍历其左子树，然后访问节点本身，最后中序遍历其右子树。由此可见，二叉搜索树的中序遍历会按字典序输出标签。需要注意的是，形状不同的二叉搜索树在中序遍历时可能产生相同的字符串序列。

在二叉搜索树中查找给定字符串$s$时，我们将$s$与根节点的标签$l$进行比较。如果$s=l$，则查找结束；否则，如果$s<l$，则继续在左子树中查找；如果$s>l$，则在右子树中查找。如果到达叶子节点，说明$s$不在树中。

这种查找过程中进行的比较次数取决于$s$和搜索树的具体形状。因此，我们希望构造一种二叉搜索树，既能存储给定的字符串序列，又能提供尽可能高效的访问。当然，我们无法提前知道哪些字符串会被查找，因此需要做一些假设。

设$n$为要存储在二叉搜索树中的字符串数量。设$K_1,\ldots,K_n$为这些字符串按字典序排列后的结果。设$p_1,\ldots,p_n$和$q_0,\ldots,q_n$为$2n+1$个非负实数，满足$\sum_{i=1}^n p_i + \sum_{i=0}^n q_i = 1$。这些数字的含义如下：

• $p_i$表示查找参数$s$为$K_i$的概率。
• $q_i$表示$s$在字典序上严格介于$K_i$和$K_{i+1}$之间的概率。

按照惯例，$q_0$表示$s$小于$K_1$的概率，$q_n$表示$s$大于$K_n$的概率。我们希望找到一个包含标签为$K_1,\ldots,K_n$的节点的二叉搜索树，使得查找时的期望比较次数最小，即：

$$\text{cost} = \sum_{i=1}^n p_i \cdot (1 + \text{内部节点} K_i \text{的层级}) + \sum_{i=0}^n q_i \cdot (\text{介于} K_i \text{和} K_{i+1} \text{之间的叶子节点的层级})。 $$

介于$K_i$和$K_{i+1}$之间的叶子节点是指在查找严格介于$K_i$和$K_{i+1}$之间的字符串$s$时到达的叶子节点。对于边界情况，遵循上述惯例。

下图展示了样例输入的第一个测试用例。图中显示了两种可能的二叉搜索树、概率以及对应的成本。

输入
输入包含多个测试用例。每个测试用例以一个整数$n$开始。假设$1 \leq n \leq 200$。接下来是$2n+1$个非负整数，表示频率。设$s$为所有频率的总和。假设$1 \leq s \leq 1000000$。概率$p_1,\ldots,p_n$和$q_0,\ldots,q_n$按顺序通过将频率除以$s$计算得到。最后一个测试用例后跟一个$0$。

输出
对于每个测试用例，设计一个二叉搜索树，使得对于指定的概率，其成本最小。输出该树的最小成本乘以$s$的整数值。

输入数据 1

2  
20 15 15 25 25  
35  
142 35 58 5 20 5 10 9 15 23 129 4 52 5 38 18 9 7 2 4 266 93 5 18 18 27 5 10 11 180 4 32 21 3 21  
0 55 27 36 85 31 58 3 334 0 98 27 113 89 180 0 62 12 0 37 0 3 64 70 0 277 0 0 0 170 0 18 76 27 3 29  
0

输出数据 1

160  
13637

来源
Ulm Local 2004