1425-快速定位


    内存限制:64MB 时间限制:1000ms 特判: No

    通过数:1 提交数:1 难度:5


题目描述:

给定n个关键字组成的有序序列S={s1s2…,sn},关键字结点称为实结点。对每个关键字查找的概率是pi,查找不成功的结点称为虚结点,对应{e0e1…,en},每个虚结点的查找概率为qie0表示小于s1的值,en大于sn的值。所有结点查找概率之和为1。求最小平均比较次数的二叉搜索树(最优二叉搜索树)。

举例说明:给定一个有序序列S={5912152024},这些数的查找概率分别是p1p2p3p4p5p6。在实际中,有可能有查找不成功的情况,例如要在序列中查找x=2,那么就会定位在5的前面,查找不成功,相当于落在了虚结点e0的位置。要在序列中查找x=18,那么就会定位在1520,查找不成功,相当于落在了虚结点e4的位置。


输入描述:

第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据第一行输入n(1 <= n <=20)为关键字个数。
第2行输入n个数,代表每个关键字的搜索概率pi(0 <= pi <=1,且∑pi+∑qi=1)。
第3行输入n+1个数,代表每个虚结点的搜索概率qi(0 <=qi <=1,且∑pi+∑qi=1)。

输出描述:

对于每一组输入,输出最优二叉搜索树的搜索成本。
每组的输出占一行。

样例输入:

2
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
4
0.05 0.1 0.3 0.08
0.2 0.06 0.01 0.13 0.07

样例输出:

2.52
1.87

提示:


上传者:rainflychxy

书中题目链接,请点击上面链接访问!

公告

    欢迎使用NYOJ2.0!