Skip to content

11077: 【原1077】加分二叉树

题目

题目描述

author: 寿鹤鸣 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1077

Description

设一个n个节点的二叉树tree的中序遍历为(l,2,3,…,n),其中数字1,2,3…,n为节点编号。

每个节点都有一个分数(均为正整数),记第j个节点的分数为di,tree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree本身)的加分计算方法如下:

    subtree的左子树的加分× subtree的右子树的加分+subtree的根的分数

若某个子树为主,规定其加分为1,叶子的加分就是叶节点本身的分数。不考虑它的空子树。

试求一棵符合中序遍历为(1,2,3,…,n)且加分最高的二叉树tree。要求输出;

(1)tree的最高加分

(2)tree的前序遍历

Input Format

第1行:一个整数n(\( n<30 \)),为节点个数

第2行:n个用空格隔开的整数,为每个节点的分数(分数<100)

Output Format

tree的最高加分。

tree的前序遍历。

Sample Input

5
5 7 1 2 10

Sample Output

145
3 1 2 4 5

FineArtz's solution

/* 加分二叉树 */
#include <iostream>
#include <cstring>
using namespace std;

int n;
int a[35] = {0}, r[35][35] = {0};
int f[35][35] = {0};

int calc(int l, int h){
    if (l > h)
        return 1;
    if (f[l][h] >= 0)
        return f[l][h];
    if (l == h){
        r[l][h] = l;
        f[l][h] = a[l];
        return f[l][h];
    }
    for (int k = l; k <= h; ++k){
        int p = calc(l, k - 1), q = calc(k + 1, h);
        if (f[l][h] < p * q + a[k]){
            f[l][h] = p * q + a[k];
            r[l][h] = k;
        }
    }
    return f[l][h];
}

void ldr(int l, int h){
    if (l > h)
        return;
    cout << r[l][h] << ' ';
    ldr(l, r[l][h] - 1);
    ldr(r[l][h] + 1, h);
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    memset(f, -1, sizeof(f));
    memset(r, -1, sizeof(r));
    calc(1, n);
    cout << f[1][n] << endl;
    ldr(1, n);
    cout << endl;
    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 100;
int DP[maxN][maxN], path[maxN][maxN], tree[maxN] = {0};

int search(int, int);

void output(int, int);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> tree[i];
    }
    cout << search(1, n) << '\n';
    output(1, n);

    return 0;
}

int search(int left, int right) {
    if (left > right) {
        return 1;
    } else if (left == right) {
        DP[left][right] = tree[left];
        path[left][right] = left;
    } else if (DP[left][right] > 0) {
        return DP[left][right];
    } else {
        for (int i = left; i <= right; i++) {
            int x = search(left, i - 1) * search(i + 1, right) + tree[i];
            if (x > DP[left][right]) {
                DP[left][right] = x;
                path[left][right] = i;
            }
        }
    }

    return DP[left][right];
}

void output(int left, int right) {
    if (left > right) {
        return;
    }

    cout << path[left][right] << ' ';
    output(left, path[left][right] - 1);
    output(path[left][right] + 1, right);
}

q4x3's solution

/**
 * dp
 * rt[l][r] 表示区间[l, r]的根
 * f[l][r] 表示区间[l, r]的加分
 **/
#include <iostream>
#include <stdio.h>

using namespace std;

int n, val[40], rt[40][40], f[40][40];

void dfs(int l, int r) {
    if(l > r) return;
    printf("%d ", rt[l][r]);
    dfs(l, rt[l][r] - 1);
    dfs(rt[l][r] + 1, r);
    return;
}

int main() {
    scanf("%d", &n);
    for(int i = 1;i <= n;++ i) {
        scanf("%d", &val[i]);
    }
    for(int i = 1;i <= n;++ i) {
        rt[i][i] = i;
        f[i][i] = val[i];
        f[i][i - 1] = 1;
    }
    for(int i = 2;i <= n;++ i) {
        for(int l = 1;l + i - 1 <= n;++ l) {
            int r = l + i - 1;
            for(int j = l;j <= r;++ j) {
                if(f[l][j - 1] * f[j + 1][r] + val[j] > f[l][r]) f[l][r] = f[l][j - 1] * f[j + 1][r] + val[j], rt[l][r] = j;
            }
        }
    }
    printf("%d\n", f[1][n]);
    dfs(1, n);
    putchar('\n');
    return 0;
}

victrid's solution

#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
long long dp[35][35] = {};
int root[35][35]     = {};
long long search(int l, int r) {
    if (l > r)
        return 1;
    if (dp[l][r] != 0)
        return dp[l][r];
    for (int i = l; i <= r; i++) {
        long long pas = search(l, i - 1) * search(i + 1, r) + search(i, i);
        if (pas > dp[l][r]) {
            dp[l][r]   = pas;
            root[l][r] = i;
        }
    }
    return dp[l][r];
}
bool isfirst = false;
void findpath(int l, int r) {
    if (l > r)
        return;
    if (l == r) {
        if (isfirst)
            putchar(' ');
        isfirst = true;
        printf("%d", l);
        return;
    }
    if (isfirst)
        putchar(' ');
    isfirst = true;
    printf("%d", root[l][r]);
    findpath(l, root[l][r] - 1);
    findpath(root[l][r] + 1, r);
    return;
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &(dp[i][i]));
    }
    printf("%lld\n", search(1, n));
    findpath(1, n);
    return 0;
}

yyong119's solution

#include <iostream>
using namespace std;

int path[35][35], p;
int dp[35][35], a[35];

int dfs(int l, int r) {

    if (dp[l][r] > 0) return dp[l][r];
    if (l > r) return 1;
    if (l == r) {
        dp[l][r] = a[l];
        path[l][r] = l;
    }
    else
    for (int i = l; i <= r; ++i) {
        int x = dfs(l, i - 1) * dfs(i + 1, r) + a[i];
        if (x > dp[l][r]) {
            dp[l][r] = x;
            path[l][r] = i;
        }
    }
    return dp[l][r];
}

void print (int l, int r) {

    if (l > r) return;
    if (p++) cout << " " << path[l][r];
    else cout << path[l][r];
    print(l, path[l][r] - 1);
    print(path[l][r] + 1, r);
}

int main() {

    int n; cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    cout << dfs(1, n) << endl;
    p = 0;
    print(1, n);
    return 0;
}