题目描述

设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：

subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数

若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。
要求输出：

（1）tree的最高加分

（2）tree的前序遍历

输入描述:

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

输出描述:

第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。
第2行：n个用空格隔开的整数，为该树的前序遍历。

示例1

输入
5
5 7 1 2 10
输出
145
3 1 2 4 5

解答

显然一道树形DP　　但与主流树形DP不同的是，本题的具体的树不是条件，而是所求。但好在题中还是给了树的中序遍历的（不然怎么做），于是想到中序遍历的性质，点A的左子树在A左，右子树在A右，再分析题意，显然对于每一个根节点A，她的树的加分在确定了左右儿子和儿子子树的最优加分后即可确定，后者由DP实现，前者则需要分别在两个备选点区间中枚举于是得出状态转移方程

剩下的就是一些个别的处理了，如当fa-1=l或fa+1=r时特别处理下，之类的。
于是本题的第一个任务完成了，剩下建棵树。这也很简单——对于和，转移自i,j，故;在DP的同时进行。

代码如下：
#include<cstdio>
using namespace std;
int n;
int a[31];
long long f[31][31][31];
int ls[31][31][31],rs[31][31][31];

long long dp(int,int,int);
void dlr(int,int,int);
int main()
{
    int i,fa;
    long long num=0,ans=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
    {
        num=dp(1,n,i);
        if(ans<num)
        {
            ans=num;
            fa=i;
        }
    }
    printf("%lld\n",ans);
    dlr(1,n,fa);
}
long long dp(int l,int r,int fa)
{
    int i,j;
    long long ans;
    if(f[fa][l][r]!=0)
        return f[fa][l][r];
    f[fa][l][r]=a[fa];
    for(i=l;i<fa;i++)
    {
        for(j=fa+1;j<=r;j++)
        {
            ans=a[fa]+dp(l,fa-1,i)*dp(fa+1,r,j);
            if(f[fa][l][r]<ans)
            {
                f[fa][l][r]=ans;
                ls[fa][l][r]=i;
                rs[fa][l][r]=j;
            }
        }
    }
    if(l==fa)
    {
        for(j=fa+1;j<=r;j++)
        {
            ans=a[fa]+dp(fa+1,r,j);
            if(f[fa][l][r]<ans)
            {
                f[fa][l][r]=ans;
                rs[fa][l][r]=j;
            }
        }
    }
    if(r==fa)
    {
        for(i=l;i<fa;i++)
        {
            ans=a[fa]+dp(l,fa-1,i);
            if(f[fa][l][r]<ans)
            {
                f[fa][l][r]=ans;
                ls[fa][l][r]=i;
            }
        }
    }
    return f[fa][l][r];
}
void dlr(int l,int r,int fa)
{
    printf("%d ",fa);
    if(ls[fa][l][r])
        dlr(l,fa-1,ls[fa][l][r]);
    if(rs[fa][l][r])
        dlr(fa+1,r,rs[fa][l][r]);
}


来源：Der Barde, Nietzsche