给定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个虚拟键搜索到的概率。 输出描述 一个实数，表示平均搜索每个结点的访问结点数的值。

解题思路： 首先根据题意可知，对于一个二叉查找树，搜索每个结点的概率等于该结点在查找路径中的层数。 假设关键字序列的长度为n，虚拟键的数量为n+1，则总的结点个数为2n+1。其中，关键字的位置从1到n，虚拟键的位置从n+2到2n+1。 可以通过动态规划来解决该问题。假设dp[i][j]表示将关键字序列从i到j构造成一棵最优二叉查找树的平均搜索结点数。 根据题意，可以将关键字分为两部分，一部分是根节点的左子树，另一部分是根节点的右子树。假设根节点的位置为k，则关键字序列从i到j的最优二叉查找树dp[i][j]可以表示为： dp[i][j] = min{dp[i][k-1] + dp[k+1][j] + sum(p[i][j])}，其中sum(p[i][j])表示关键字序列从i到j的概率之和，即sum(p[i][j]) = p[i]+p[i+1]+...+p[j]。 在计算dp[i][j]时，需要计算sum(p[i][j])。可以用一个辅助数组sum计算sum(p[i][j])的值。sum[i][j]表示关键字序列从i到j的概率之和。 辅助数组sum的计算可以通过动态规划来实现。假设sum[i][j]表示关键字序列从i到j的概率之和，可得： sum[i][j] = sum[i][j-1] + p[j]，当i <= j时； sum[i][j] = q[i-j-1]，当i = j+1时； sum[i][j] = sum[i][j-1] + q[i-j-1]，当i > j+1时。 返回dp[1][n]的值即可。 具体实现步骤如下： 1. 读入n和n个关键字的概率pi。 2. 读入n+1个虚拟键的概率qi。 3. 初始化dp和sum数组，大小为2n+1。 4. 计算sum数组的值。 5. 动态规划求解dp数组。 6. 输出dp[1][n]的值。 下面是具体的Java实现代码： ```java import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); double[] p = new double[n]; for (int i = 0; i < n; i++) { p[i] = scanner.nextDouble(); } double[] q = new double[n + 1]; for (int i = 0; i <= n; i++) { q[i] = scanner.nextDouble(); } double[][] dp = new double[2 * n + 1][2 * n + 1]; double[][] sum = new double[2 * n + 1][2 * n + 1]; for (int i = 1; i <= 2 * n; i++) { sum[i][i - 1] = q[i - 1]; dp[i][i] = p[i - 1] + q[i - 1] + q[i]; sum[i][i] = dp[i][i]; } for (int len = 2; len <= n + 1; len++) { for (int i = 1, j = i + len - 1; j <= 2 * n; i++, j++) { sum[i][j] = sum[i][j - 1] + p[j - 1] + q[j]; dp[i][j] = Double.MAX_VALUE; for (int k = i; k <= j; k++) { dp[i][j] = Math.min(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + sum[i][j]); } } } System.out.println(dp[1][n]); } } ``` 复杂度分析： 动态规划求解dp数组的时间复杂度为O(n^3)，其中n为关键字的个数。遍历dp数组共有(2n+1)^2个元素，因此总的时间复杂度为O(n^3)。 空间复杂度为O(n^2)，需要两个二维数组dp和sum来保存中间结果。 [2024-06-09 18:22:50 | AI写代码神器 | 1749点数解答]