给定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个关键字构造的最优二叉查找树的平均搜索结点数。初始化dp数组为0。 然后使用两层循环，外层循环从小到大遍历关键字的范围，内层循环遍历可能的根节点。对于dp[i][j]，假设根节点是k，则左子树范围是(i, k-1)，右子树范围是(k+1, j)。计算dp[i][j]的方法如下： 1. 对于关键字ki到kj之间的实际关键字，累加它们的概率，得到sum_p = sum(pi + pi+1 + ... + pj)。 2. 对于虚拟键di到dj之间的虚拟键，累加它们的概率，得到sum_q = sum(qi + qi+1 + ... + qj)。 3. 对于根节点k，搜索到的结点总数为sum_p + sum_q，左子树的结点总数为dp[i][k-1]，右子树的结点总数为dp[k+1][j]，因此dp[i][j] = sum_p + sum_q + dp[i][k-1] + dp[k+1][j]。 4. 这里需要注意的是，如果左子树或右子树为空，即k-1 < i或k+1 > j，那么dp[i][k-1]或dp[k+1][j]应该为0。 最终的答案为dp[1][n]，即从第1个关键字到第n个关键字构造的最优二叉查找树的平均搜索结点数。 [2024-06-07 16:14:48 | AI写代码神器 | 584点数解答]