题面

最优二叉搜索树是由 n 个键和 n+1 个虚拟键构造的二叉搜索树，以最小化搜索操作的成本期望值。
给定一个序列 K=k1​,k2​,...,kn​，其中 n 个不同的键按排序顺序 ，我们希望构造一个二叉搜索树。 对于每个关键 ki​，我们有一个概率 pi​，搜索将是ki​。 一些搜索可能针对不在 K 中的值，因此我们还有 n+1 个虚拟键 d0​,d1​,d2​,...,dn​ 表示不在 K 中的值。虚拟键 di​(0≤i≤n) 被定义 如下：

• 如果 i=0，则 di​ 表示所有小于 k1​ 的值
• 如果 i=n，则 di​表示所有大于 kn​ 的值。
• 如果 1≤i≤n−1，则 di​表示 ki​ 和 ki+1​ 之间

对于每个虚拟键 di​，我们有一个搜索将对应于 di 的概率 qi。 对于 pi​(1≤i≤n) 和 qi​(0≤i≤n)，我们有

那么在二叉搜索树 T 中搜索的期望成本是

其中depthT(v)是T中节点v的深度。对于给定的一组概率，我们的目标是构造一个期望搜索成本最小的二叉搜索树。 我们称这样的树为最优二叉搜索树。
每个密钥 ki 是一个内部节点，每个虚拟密钥 di 是一个叶子。 例如，下图显示了从样本输入 1 中得到的最优二叉搜索树。

任务
编写一个程序，计算通过给定 pi​ 获得的最优二叉搜索树上的搜索操作的期望值，搜索将针对 ki​ 和 qi​，搜索将对应于 di​。

输入

第一行，给出一个整数 n，表示键的数量。
第二行，pi​(1≤i≤n) 以具有四位小数的实数给出。
第三行，qi​(0≤i≤n) 以实数形式给出，小数点后四位。

1≤n≤500
0<pi​,qi​<1
∑i=1n​pi​+∑i=0n​qi​=1

输出

在一行中打印最优二叉搜索树上搜索操作的期望值。 输出误差不大于10^−4

输入样例

 5
0.1500 0.1000 0.0500 0.1000 0.2000
0.0500 0.1000 0.0500 0.0500 0.0500 0.1000

输出样例

2.75000000 

代码

 

#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
 
using namespace std;
 
const double MaxVal = 1e18;
 
void optimalBST(double *p, double *q, int n, vector<vector<double>>& e, vector<vector<int>>& root, vector<vector<double>>& w) {
    // 初始化只包括虚拟键的子树
    for (int i = 1; i <= n + 1; ++i) {
        w[i][i - 1] = q[i - 1];
        e[i][i - 1] = q[i - 1];
    }
 
    // 由下到上，由左到右逐步计算
    for (int len = 1; len <= n; ++len) {
        for (int i = 1; i <= n - len + 1; ++i) {
            int j = i + len - 1;
            e[i][j] = MaxVal;
            w[i][j] = w[i][j - 1] + p[j] + q[j];
            // 求取最小代价的子树的根
            for (int k = i; k <= j; ++k) {
                double temp = e[i][k - 1] + e[k + 1][j] + w[i][j];
                if (temp < e[i][j]) {
                    e[i][j] = temp;
                    root[i][j] = k;
                }
            }
        }
    }
}
 
int main() {
    int n;
    cin >> n;
 
    double* p = new double[n + 1];
    double* q = new double[n + 1];
 
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
    }
    for (int i = 0; i <= n; ++i) {
        cin >> q[i];
    }
 
    vector<vector<double>> e(n + 2, vector<double>(n + 2, 0.0));
    vector<vector<int>> root(n + 2, vector<int>(n + 2, 0));
    vector<vector<double>> w(n + 2, vector<double>(n + 2, 0.0));
 
    optimalBST(p, q, n, e, root, w);
 
    cout << fixed << setprecision(10) << e[1][n] << endl;
 
    delete[] p;
    delete[] q;
 
    return 0;
}