3895: 4.10 快速定位——最优二叉搜索树

给定 n 个关键字组成的有序序列 S={s1，s2，…，sn}，关键字结点称为实结点。对每个 关键字查找的概率是 pi，查找不成功的结点称为虚结点，对应{e0，e1，…，en}，每个虚结 点的查找概率为 qi。e0表示小于 s1的值，en大于 sn的值。所有结点查找概率之和为 1。求最 小平均比较次数的二叉搜索树（最优二叉搜索树）。 举例说明：给定一个有序序列 S={5，9，12，15，20，24}，这些数的查找概率分别为p1、p2、p3、p4、p5、p6。在实际中，有可能有查找不成功的情况，例如要在序列中查找 x=2， 那么我们就会定位在 5 的前面，查找不成功，相当于落在了虚结点 e0 的位置。要在序列中 查找 x=18，那么就会定位在 15～20，查找不成功，相当于落在了虚结点 e4的位置

输入一个T，T代表有T组数据（1<=T<=10）

输入关键字的个数n(1<=n<=10)

依次输入每个关键字的搜索概率

依次输入每个虚结点的搜索概率

输出小的搜索成本是多少

1
6
0.04 0.09 0.08 0.02 0.12 0.14 
0.06 0.08 0.10 0.07 0.05 0.05 0.10 

2.52