最优二叉搜索树【东北大学oj数据结构10-4】C++
题面
最优二叉搜索树是由 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=1npi+∑i=0nqi=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;
}