创业中文网站模板,商城网站设计定制,重庆网站推广计划,自己开店题面
最优二叉搜索树是由 n 个键和 n1 个虚拟键构造的二叉搜索树#xff0c;以最小化搜索操作的成本期望值。 给定一个序列 Kk1,k2,...,kn#xff0c;其中 n 个不同的键按排序顺序 #xff0c;我们希望构造一个二叉搜索树。 对于每个关键 ki#xff0c;我们有一个…题面
最优二叉搜索树是由 n 个键和 n1 个虚拟键构造的二叉搜索树以最小化搜索操作的成本期望值。 给定一个序列 Kk1,k2,...,kn其中 n 个不同的键按排序顺序 我们希望构造一个二叉搜索树。 对于每个关键 ki我们有一个概率 pi搜索将是ki。 一些搜索可能针对不在 K 中的值因此我们还有 n1 个虚拟键 d0,d1,d2,...,dn 表示不在 K 中的值。虚拟键 di(0≤i≤n) 被定义 如下
如果 i0则 di 表示所有小于 k1 的值如果 in则 di表示所有大于 kn 的值。如果 1≤i≤n−1则 di表示 ki 和 ki1 之间
对于每个虚拟键 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 0pi,qi1 ∑i1npi∑i0nqi1
输出
在一行中打印最优二叉搜索树上搜索操作的期望值。 输出误差不大于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 algorithmusing namespace std;const double MaxVal 1e18;void optimalBST(double *p, double *q, int n, vectorvectordouble e, vectorvectorint root, vectorvectordouble 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];}vectorvectordouble e(n 2, vectordouble(n 2, 0.0));vectorvectorint root(n 2, vectorint(n 2, 0));vectorvectordouble w(n 2, vectordouble(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;
}
