算法设计与分析

最优搜索树

动态规划典型题(1)- 最优二叉搜索树

Description

众所周知,二叉搜索树能将序列上o(n)的查找,转化为二叉树形结构上o(logn)的分治。但现在如果我们已经知道序列上所有点访问的概率。那么我们就可以把概率高点的路径变短,概率低的路径增长(看起来有点像霍夫曼树)。那么问题来了:

给定一组有序的序列K,在查找的过程中被查找的键是k_i的概率是p_i。用这个序列构成一颗二叉搜素树。那么这颗二叉搜索树的每次查找深度期望的最小值是多少?

Input

第一行一个整数T(<=20),代表测试样例的组数。

接下来的每组case:

第一行一个整数n(<=100),代表序列长度。

第二场n个整数pi,代表每个点访问的概率,且所有点概率和为1。

Output

输出一个浮点数,代表最小的深度期望(保留小数点后6位)。

Sample Input

1 4 0.5 0.1 0.2 0.2

Sample Output

1.800000