给定标识符集(a 1 ​ , a 2 ​ , …a n ​ )，这些字符的下标从1开始按自然序编号，p i ​ 是对a i ​ 成功检索的概率, q i ​ 是不成功检索的概率, 且∑ (1<=i<=n) ​ p i ​ +∑ (0<=i<=n) ​ q i ​ =1，问:它的最优二分检索树是怎样的？ 输入格式: 第1行是n，表示字符个数； 第2行是这n个字符的成功检索概率p i ​ , 0<p i ​ <1; 第3行是失败检索概率q i ​ ，0<q i ​ <1，且∑ (1<=i<=n) ​ p i ​ +∑ (0<=i<=n) ​ q i ​ =1。 输出格式: 最优二分检索树先根遍历时得到的字符编号序列。

这是一道经典的动态规划问题，可以使用动态规划算法求解。

假设我们要构建一棵最优二分检索树，我们可以先将所有的字符按照自然序编号排序，然后对于每一段连续的字符子序列，我们需要选择一个节点作为根节点，使得查询这个节点的概率最小。假设我们选择第k个字符作为根节点，则它的左子树包含编号为1到k-1的字符，右子树包含编号为k+1到n的字符。因此，我们需要计算出在这个字符子序列中选择每一个字符作为根节点的最小查询概率，然后取最小值作为整个子序列的最小查询概率。

为了方便计算，我们可以定义一个二维数组dp[i][j]表示从第i个字符到第j个字符构成的字符子序列的最小查询概率。对于每个dp[i][j]，我们可以枚举k=i到j，计算出选择第k个字符作为根节点的最小查询概率，然后取最小值作为dp[i][j]的值。具体地，我们可以使用以下的递推公式：

dp[i][j] = min(dp[i][k-1] + dp[k+1][j] + sum(p[i...j]) + sum(q[i-1...j]))

其中sum(p[i...j])表示从第i个到第j个字符的成功查询概率之和，sum(q[i-1...j])表示从第i-1个到第j个字符的失败查询概率之和。上述公式中，dp[i][k-1]和dp[k+1][j]分别表示左子树和右子树的最小查询概率，两者的和加上当前节点的查询概率就是选择第k个字符作为根节点的最小查询概率。

最终的答案就是dp[1][n]，也就是从第1个字符到第n个字符构成的整个字符序列的最小查询概率。

在计算dp数组的过程中，我们还需要记录一下每个节点的父亲节点，以便后续输出最优二分检索树的先根遍历序列。

下面是Java代码实现：

import java.util.*;

public class Main {
    static int n;
    static double[] p, q;
    static double[][] dp;
    static int[][] root;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        p = new double[n + 1];
        q = new double[n + 1];
        dp = new double[n + 1][n + 1];
        root = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            p[i] = scanner.nextDouble();
        }
        for (int i = 0; i <= n; i++) {
            q[i] = scanner.nextDouble();
        }

        // 初始化dp数组
        for (int i = 1; i <= n; i++) {
            dp[i][i] = p[i] + q[i-1] + q[i];
            root[i][i] = i;
        }
        for (int len = 2; len <= n; len++) {
            for (int i = 1; i <= n - len + 1; i++) {
                int j = i + len - 1;
                dp[i][j] = Double.MAX_VALUE;
                for (int k = i; k <= j; k++) {
                    double val = dp[i][k-1] + dp[k+1][j] + sum(p, i, j) + sum(q, i-1, j);
                    if (val < dp[i][j]) {
                        dp[i][j] = val;
                        root[i][j] = k;
                    }
                }
            }
        }

        // 输出先根遍历序列
        List<Integer> preorder = new ArrayList<>();
        preorderTraversal(preorder, 1, n);
        for (int i : preorder) {
            System.out.print(i + " ");
        }
    }

    static double sum(double[] arr, int i, int j) {
        double res = 0;
        for (int k = i; k <= j; k++) {
            res += arr[k];
        }
        return res;
    }

    static void preorderTraversal(List<Integer> preorder, int i, int j) {
        if (i > j) return;
        preorder.add(root[i][j]);
        preorderTraversal(preorder, i, root[i][j]-1);
        preorderTraversal(preorder, root[i][j]+1, j);
    }
}

时间复杂度为O(n^3)。