给定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个虚拟键搜索到的概率。输出描述 一个实数，表示平均搜索每个结点的访问结点数的值。输入样例 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) f = [[0] * (n + 2) for _ in range(n + 2)] w = [[0] * (n + 2) for _ in range(n + 2)] for i in range(1, n + 1): w[i][i] = p[i - 1] for j in range(i + 1, n + 2): w[i][j] = w[i][j - 1] + p[j - 2] for l in range(2, n + 2): for i in range(1, n + 2 - l): j = i + l f[i][j] = float('inf') for r in range(i, j): f[i][j] = min(f[i][j], f[i][r] + f[r + 1][j] + w[i][j]) return f[1][n + 1] / (sum(p) + sum(q)) p = list(map(float, input().split())) q = list(map(float, input().split())) result = optimal_bst(p, q) print("{:.2f}".format(result)) ``` 输入样例： ``` 15 0.1 0.05 0.1 0.2 0.05 0.1 0.05 0.05 0.05 0.1 ``` 输出样例： ``` 一个实数，保留两位小数结果值 ``` [2024-06-09 16:12:27 | AI写代码神器 | 450点数解答]