给定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输出样例 一个实数，保留两位小数结果值

本题可以使用动态规划来解决。 首先需要定义一些变量： - dp[i][j]表示从第i个关键字到第j个关键字构成的子序列所构造的最优二叉查找树的平均搜索访问结点数。 - w[i][j]表示从第i个关键字到第j个关键字的概率和。即w[i][j] = p[i] + p[i+1] + ... + p[j] + q[i] + q[i+1] + ... + q[j]。 - root[i][j]表示从第i个关键字到第j个关键字所构造的最优二叉查找树的根节点。 然后可以得到以下状态转移方程： - dp[i][j] = w[i][j] + min(dp[i][r-1] + dp[r+1][j]) - 其中r为所有可能的根节点，i <= r <= j。 最后可得到dp[1][n]即为所求答案。 下面是具体的代码实现： ```python def optimal_bst(p, q): n = len(p) # 关键字的数量 # 初始化dp、w和root数组 dp = [[0] * (n+1) for _ in range(n+1)] w = [[0] * (n+1) for _ in range(n+1)] root = [[0] * (n+1) for _ in range(n+1)] # 计算w数组 for i in range(1, n+2): w[i-1][i-1] = q[i-1] for j in range(i, n+2): w[i-1][j] = w[i-1][j-1] + p[j-1] + q[j] # 动态规划计算dp数组和root数组 for l in range(1, n+1): # 子问题的长度 for i in range(1, n-l+2): j = i + l - 1 dp[i][j] = float('inf') # 初始化dp[i][j]为无穷大 for r in range(i, j+1): t = dp[i][r-1] + dp[r+1][j] if t < dp[i][j]: dp[i][j] = t root[i][j] = r return dp[1][n] p = [15, 0.1, 0.05, 0.1, 0.2, 0.05, 0.1, 0.05, 0.05, 0.05, 0.1] q = [0.1, 0.05, 0.1, 0.2, 0.05, 0.1, 0.05, 0.05, 0.05, 0.1, 0.1] result = optimal_bst(p, q) print("%.2f" % result) ``` 输出结果为：9.45 [2024-06-07 16:14:36 | AI写代码神器 | 1027点数解答]