加分二叉树

题意：给出一个n个节点的二叉树，中序遍历为1，2，3,......，n;每个节点都有一个分数（均为正整数），任一棵子树subtree的加分计算方法如下：
subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数
求二叉树的最大分数和前序遍历？

思路：f[i][j]为从第i个到第j个节点的树最高分.
root[i][j]为从第i个到第j个节点的数根节点.
f[i][j]=max{f[i][o-1]*f[o+1][j]+f[o][o]}(o>=i,o<=j)

代码：

#include<bits/stdc++.h>
#define ll long long

using namespace std;

int f[105][105], d[105][105], ans=0;

void dfs(int i, int j)  //前序遍历
{
    if(i>=j)
    {
        if(i==j)
        {
            printf("%c%d",ans==0?'\0':' ',i);
        }
        ans++;
        return ;
    }
    int v=d[i][j];
    if(ans!=0)
        printf(" %d",v);
    else
    {
        printf("%d",v);
    }
    ans++;
    dfs(i,v-1);
    dfs(v+1,j);
}

int main()
{
    int n;
    scanf("%d",&n);
    memset(d,-1,sizeof(d));
    for(int i=1; i<=n; i++) //初始化
    {
        scanf("%d",&f[i][i]);
        f[i][i-1]=1;
        f[i+1][i]=1;
    }
    for(int i=n;i>=1;i--) 
    {
        for(int j=i+1;j<=n;j++)
        {
            for(int o=i; o<=j; o++)
            {
                if(f[i][j]<f[i][o-1]*f[o+1][j]+f[o][o])
                {
                    f[i][j]=f[i][o-1]*f[o+1][j]+f[o][o];
                    d[i][j]=o;
                }
            }
        }
    }
    printf("%d\n",f[1][n]);
    dfs(1,n);
    printf("\n");
    return 0;
}