题目描述

设一个 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 行：一个整数 n，为节点个数。 

第 2 行：n 个用空格隔开的整数，为每个节点的分数（0<分数<100）。

输出格式
第 1 行：一个整数，为最高加分（结果不会超过int范围）。     

第 2 行：n 个用空格隔开的整数，为该树的前序遍历。如果存在多种方案，则输出字典序最小的方案。

数据范围
n<30

样例

输入样例：

5
5 7 1 2 10

输出样例：

145
3 1 2 4 5

思路讲解

由于是中序遍历，而中序下的一棵树的表达方式是：左子树的中序遍历+根节点+右子树的中序遍历，所以只要选取一段区间$[l,r]$的一个点$k$，将$[l,k-1]$分最大值,$[k+1,r]$分最大值相乘再加上$a[k]$就是该区间以k作为该子树根节点的最大值，所以就是板子了，关于答案输出的问题，每一次记录下$[l,r]$分最大时的根节点，最后递归输出即可^^

#include<bits/stdc++.h>
using namespace std;
int dp[101][101],a[101],father[101][101];
int mmax(int a,int b,int l,int r,int root){
    if(a<b){
        father[l][r]=root;
        return b;
    }else{
        return a;
    }
}
void print(int l,int r){
    if(l>r){
        return;
    }
    cout<<father[l][r]<<" ";
    print(l,father[l][r]-1);
    print(father[l][r]+1,r); 
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int len=1;len<=n;len++){
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            for(int k=l;k<=r;k++){
                int lson=l==k?1:dp[l][k-1];
                int rson=r==k?1:dp[k+1][r];
                dp[l][r]=mmax(dp[l][r],(l!=r)*(lson*rson)+a[k],l,r,k);
            } 
        }
    }
    cout<<dp[1][n]<<endl;
    print(1,n);
}