最优二叉搜索树

5月5日 · 2018年

最优二叉搜索树

教材已经把每一步的推导写的很清楚了

只要把伪代码实现了就可以了

分析从略,代码如下

#include <bits/stdc++.h>

#define MAXN 1007
#define POSITIVE_INFINITY 0X3F3F3F

int n;
double p[MAXN] = {0};
double q[MAXN] = {0};
double e[MAXN][MAXN] = {0};
double w[MAXN][MAXN] = {0};


int main() {

    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]);

    for (int i = 1; i <= n + 1; ++i)
        e[i][i - 1] = w[i][i - 1] = q[i - 1];
    for (int l = 1; l <= n; ++l)
        for (int i = 1; i <= n - l + 1; ++i) {
            int j = i + l - 1;
            e[i][j] = POSITIVE_INFINITY;
            w[i][j] = w[i][j - 1] + p[j] + q[j];
            for (int r = i; r <= j; ++r) {
                double t = e[i][r - 1] + e[r + 1][j] + w[i][j];
                if (t < e[i][j])
                    e[i][j] = t;
            }
        }
    std::cout << e[1][n] << std::endl;
    return 0;
}

0 条回应
验证码
输入运算符及数字使等式成立
{{comment.validate_num1}} = {{comment.validate_num2}}
点赞确定
退出登录?
取消 确定