解题报告 P1040 加分二叉树【NOIP2003TG】

题目内容

P1040

大意：给出一个中序遍历为 1,2,\dots,n 的二叉树，记节点 i 的分数为 d_i，定义子树 subtree 的分数为左子树的加分乘右子树的加分加根的分数。求最大加分以及该情况下树的前序遍历。

解题思路

首先，只给了一个中序遍历是无法确定一棵二叉树的，这就导致了不同的二叉树有着不同的加分，我们只需要求出这最大的加分就可以了。

一棵子树的中序遍历有一个性质：选定根节点后，中序遍历左边的点一定在左子树中，右边的一定在右子树中，这就导致了我们可以递归进行求解，每次都枚举根节点。

设 f(i,j) 表示从 i 到 j 的节点构成的子树的最大加分，其中 i。很明显读入的时候即可确定 f(i,i) 就是这个节点的分数，然后是状态转移方程：

f(i,j)=\max_{i\le k\le j}\lbrace f(i,k-1)\times f(k+1,j)+f(k,k)\rbrace

这个状态转移方程意思就是当前递归到子树 i,j 时，枚举所有可能存在的根节点 k，然后进行下一步的递归，在整个过程中寻找可达到的最大加分并记录。最后输出 f(1,n) 即可。

然后就是如何输出前序遍历的问题了，其实在上一步进行状态转移的时候就可以记录下可以使得子树加分最大的根节点，然后记录下来之后依次按照这样递归遍历就可以了。

上述过程中注意判断边界条件，当 i>j 时就要停止

#include <cstdio>
#include <cstring>
typedef long long ll;

ll n,f[32][32],root[32][32];
//f的定义见上，root[i][j]表示可以使得子树 i,j 加分最大的根节点的编号

ll search(int l,int r)
{
    ll now;//存储当前状态
    if(l>r)//如果遍历到空子树
        return 1;//返回1
    if(f[l][r]==-1)//如果这个子树还没有进行过处理
        for(int k=l;k<=r;k++)//枚举所有可能存在的根节点
        {
            now=search(l,k-1)*search(k+1,r)+f[k][k];//更新当前状态
            if(now>f[l][r])//如果可以更大
                f[l][r]=now,root[l][r]=k;//更新，并记录根节点
        }
    return f[l][r];//返回上级
}

void preorder(int l,int r)
{
    if(l>r)//如果空了
        return;
    int k=root[l][r];
    printf("%d ",k);//打印根
    preorder(l,k-1);//遍历左
    preorder(k+1,r);//遍历右
    return;
}

int main()
{
    scanf("%lld",&n);
    memset(f,-1,sizeof(f));//先将所有标记为未访问
    for(int i=1;i<=n;i++)
        scanf("%lld",&f[i][i]),root[i][i]=i;
    printf("%lld\n",search(1,n));//输出最大加分
    preorder(1,n);//遍历子树
    return 0;
}