题目描述

设一个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的前序遍历

思路

设t[i][j]为区间i到j的最大加分
枚举距离为d的两个节点构成的最大加分
然后枚举根节点，dp是记录点根节点root
方程我已经不会写了。。。。

#include <stdio.h>
#define maxn 31
using namespace std;
int t[maxn][maxn],root[maxn][maxn],a[maxn];
inline int read()
{
    int x=0,p=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-')p=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*p;
}
int print(int p1,int p2)
{
    if (p2>=p1)
    {
        printf("%d ",root[p1][p2]);
        print(p1,root[p1][p2]-1);
        print(root[p1][p2]+1,p2);
    }
}
int main()
{
    int n=read();
    for (int i=1;i<=n;i++)
        a[i]=read();
    for (int i=1;i<=n;i++)
    {
        t[i][i]=a[i];
        root[i][i]=i;
    }
    for (int i=1;i<=n-1;i++)
    {
        t[i][i+1]=a[i]+a[i+1];
        root[i][i+1]=i;
    }
    for (int d=2;d<=n-1;d++)
        for (int i=1;i<=n-d;i++)
        {
            int s=t[i][i]+t[i+1][i+d];
            root[i][i+d]=i;
            for (int j=1;j<=d;j++)
            {
                int temp=t[i+j][i+j]+t[i][i+j-1]*t[i+j+1][i+d];
                if (temp>s) 
                {
                    s=temp;
                    root[i][i+d]=i+j;
                }
            }
            int temp=t[i][i+d-1]+t[i+d][i+d];
            if (temp>s)
            {
                s=temp;
                root[i][i+d]=i+d+1;
            }
            t[i][i+d]=s;
        }
    printf("%d\n",t[1][n]);
    print(1,n);
}