2021秋季《数据结构》_EOJ 1075.最优二叉搜索树

题目

思路

参考这篇博客和这篇博客
大体思路见注释。

代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1002
#define INFIN 5000double p[MAXN] = {
     0 };  // 结点查找概率
double q[MAXN] = {
     0 };  // 伪关键字查找概率
double e[MAXN][MAXN] = {
     {
    0} };
// e[i][j]表示从结点i到结点j构成的最有查找树的概率期望
int root[MAXN][MAXN] = {
     {
    0} };
// root[i][j]表示从结点i到结点j构成的最有查找树的根节点
double w[MAXN][MAXN] = {
     {
    0} };
// w[i][j]表示从区间i到j的概率和void optimalBST(double p[], double q[], int n)
{
    // 只包含伪结点的子树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] = INFIN;w[i][j] = w[i][j - 1] + p[j] + q[j];// 遍历每个结点作为根节点的情况，找到总代价最小的一个for (int r = i; r <= j; r++){
    double tmp = e[i][r - 1] + e[r + 1][j] + w[i][j];if (tmp < e[i][j]){
    e[i][j] = tmp;root[i][j] = r;}}}}
}int main()
{
    int n; cin >> n;for (int i = 1; i <= n; i++){
    cin >> p[i];}for (int i = 0; i <= n; i++){
    cin >> q[i];}optimalBST(p, q, n);cout.setf(ios::fixed);cout << setprecision(6) << e[1][n] << endl;return 0;
}