写出上述问题的c++实现代码，输出M行正整数，第i行表示第i组数据的最优二叉搜索树的期望代价, 保留小数点后6位。

以下是对应的C++代码实现：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 505;

int n;
double p[MAXN], q[MAXN], f[MAXN][MAXN], sum[MAXN][MAXN];
int g[MAXN][MAXN];

double dp() {
    for (int i = 1; i <= n + 1; i++) {
        f[i][i - 1] = q[i - 1];
        sum[i][i - 1] = q[i - 1];
        g[i][i - 1] = i - 1;
    }
    for (int len = 1; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            f[i][j] = 1e18;
            for (int k = i; k <= j; k++) {
                double tmp = f[i][k - 1] + f[k + 1][j] + sum[i][j];
                if (tmp < f[i][j]) {
                    f[i][j] = tmp;
                    g[i][j] = k;
                }
            }
            sum[i][j] = sum[i][j - 1] + p[j] + q[j];
        }
    }
    return f[1][n];
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%lf", &p[i]);
        }
        for (int i = 0; i <= n; i++) {
            scanf("%lf", &q[i]);
        }
        printf("%.6lf\n", dp());
    }
    return 0;
}

其中，变量p[i]表示第i个关键字的搜索概率，q[i]表示第i个区间的搜索概率。函数dp()返回最优二叉搜索树的期望代价。在主函数中，t表示数据组数，按顺序读入每组数据并输出最优二叉搜索树的期望代价。