给定n个互异的关键字组成的序列k=<k1,k2,...,kn>，且关键字有序（k1<k2<...<kn），从这些关键字中构造一棵二叉查找树。对每个关键字ki，每次搜索到的概率为pi。还有n+1个“虚拟键”d0,d1,...,dn，他们代表不在k的值。d0代表所有小于k1的值，dn代表所有大于kn的值，对于i = 1,2,...,n-1,虚拟键di代表位于ki和ki+1之间的值。对于每个di，每次搜索di的概率为qi。要求建立一棵最优二叉查找树，使所有的搜索操作访问的结点总数最少，并输出平均搜索每个结点的访问结点数的值。 输入描述 第一行n个实数p1,p2...pn， 表示k1,k2,...kn搜索到的概率。 第二行n+1个实数d0,d1,...dn, 表示 n+1个虚拟键搜索到的概率。 输出描述 一个实数，表示平均搜索每个结点的访问结点数的值。 输入样例 0.15 0.1 0.05 0.1 0.2 0.05 0.1 0.05 0.05 0.05 0.1 输出样例 一个实数，保留两位小数结果值。

解析：首先需要计算每个关键字和虚拟键的搜索概率之和，然后根据这些概率构建最优二叉查找树，最后计算平均搜索每个结点的访问结点数的值。 代码如下： ```python def optimal_bst(p, q): n = len(p) m = [[0] * (n + 1) for _ in range(n + 2)] w = [[0] * (n + 1) for _ in range(n + 1)] for i in range(1, n + 2): m[i][i - 1] = q[i - 1] w[i - 1][i - 1] = q[i - 1] for l in range(1, n + 1): for i in range(1, n - l + 2): j = i + l - 1 m[i][j] = min([m[i][r - 1] + m[r + 1][j] for r in range(i, j + 1)]) + sum(p[i - 1:j]) w[i][j] = w[i][r - 1] + p[r - 1] + w[r + 1][j] for r in range(i, j + 1): if m[i][j] == m[i][r - 1] + m[r + 1][j] + sum(p[i - 1:j]): break return m[1][n], w[1][n] / m[1][n] p = list(map(float, input().split())) q = list(map(float, input().split())) _, result = optimal_bst(p, q) print("{:.2f}".format(result)) ``` 输入样例： ``` 0.15 0.1 0.05 0.1 0.2 0.05 0.1 0.05 0.05 0.05 0.1 ``` 输出样例： ``` 一个实数，保留两位小数结果值。 ``` [2024-06-09 02:46:12 | AI写代码神器 | 526点数解答]