加分二叉树

题目描述

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

题解：

f[i][j]来表示节点i到节点j成树的最大加分
f[i][i]=a[i]其中a[i]为第i个节点的分数。
分数 = 左子树 * 右子树 +根
那我们只需要知道左右子树的分数和根的分数就可以了，至于树长什么样并不关心
我们枚举根节点k
f[i][j] = f[i][k-1] * f[k+1][j] + f[k][k];
为了后面前序遍历的实现，我们用root[i][j]来表示节点i到节点j成树的最大加法所选的根节点
前序遍历：中前后

代码：

#include<iostream>
#include<cstdio>
using namespace std;
int n,v[39],f[47][47],i,j,k,root[49][49];
void print(int l,int r){
    if(l>r)return;
    if(l==r){printf("%d ",l);return;}
    printf("%d ",root[l][r]);
    print(l,root[l][r]-1);
    print(root[l][r]+1,r);
}
int main() {
    scanf("%d",&n);
    for( i=1; i<=n; i++) scanf("%d",&v[i]);
    for(i=1; i<=n; i++) {f[i][i]=v[i]; f[i][i-1]=1;}

    for(i=n; i>=1; i--)
        for(j=i+1; j<=n; j++)
            for(k=i; k<=j; k++) 
            {
                if(f[i][j]<(f[i][k-1]*f[k+1][j]+f[k][k])) {
                    f[i][j]=f[i][k-1]*f[k+1][j]+f[k][k];
                    root[i][j]=k;
                }
            }
    printf("%d\n",f[1][n]);
    print(1,n);
    return 0;
}