难度：普及+/提高

题目描述

        设一个n个节点的二叉树tree的中序遍历为(1，2，3，… ，n)，其中数字1，2，3，… ，n为节点编号。每个节点都有一个分数(均为正整数)，记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree(也包含tree本身)的加分计算方法如下:
        subtree的左子树的加分 × subtree的右子树的加分＋subtree的根的分数。
        若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。
        试求一棵符合中序遍历为(1，2，3，… ，n)且加分最高的二叉树tree。要求输出;
        (1)tree的最高加分
        (2)tree的前序遍历

输入输出格式

输入格式:

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

输出格式:

        第1行:1个整数，为最高加分(Ans≤4，000，000，000)。
        第2行:n个用空格隔开的整数，为该树的前序遍历。

输入输出样例

Sample input

5
5 7 1 2 10

Sample output

145
3 1 2 4 5

题解

        题目考察树型动态规划和二叉树遍历。
        设f(x，y)表示中序遍历为x，x+1，…，y-1，y的子树的最高加分，则有:

        递推即得结果。
        第二问可以设置一个数组tree[x][y]表示x~y的子树的根节点，递归遍历可得前序遍历序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>

using namespace std;
int op[50], n;
int rem[50][50] = {0};
int tree[50][50] = {0};

int DP(int x, int y) {
    if (x > y)return 1;
    if (x == y)return op[x];
    if (rem[x][y] != 0)return rem[x][y];
    int ans = 0;
    for (register int i = x; i <= y; i++)
        if (DP(x, i - 1) * DP(i + 1, y) + op[i] > ans)
            ans = DP(x, i - 1) * DP(i + 1, y) + op[i], tree[x][y] = i;
    return rem[x][y] = ans;
}

void print(int x, int y) {
    if (x > y)return;
    if (x == y) {
        cout << x << '\x20';
        return;
    }
    cout << tree[x][y] << '\x20';
    print(x, tree[x][y] - 1);
    print(tree[x][y] + 1, y);
}

int main() {
    cin >> n;
    for (register int i = 1; i <= n; i++)cin >> op[i];
    cout << DP(1, n) << endl;
    print(1, n);
    return 0;
}