【算法•日更•第十期】树型动态规划&区间动态规划：加分二叉树题解

　　废话不多说，直接上题：

---

1580：加分二叉树

时间限制: 1000 ms         内存限制: 524288 KB
提交数: 121     通过数: 91 

【题目描述】

原题来自：NOIP 2003

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

记 subtree 的左子树加分为 l，右子树加分为 r，subtree 的根的分数为 a，则 subtree 的加分为：

l×r+a

若某个子树为空，规定其加分为 1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。

试求一棵符合中序遍历为 (1,2,3,⋯,n) 且加分最高的二叉树 tree。

要求输出：

1、tree 的最高加分；

2、tree 的前序遍历。

【输入】

第一行一个整数 n 表示节点个数；

第二行 n 个空格隔开的整数，表示各节点的分数。

【输出】

第一行一个整数，为最高加分 b；

第二行 n 个用空格隔开的整数，为该树的前序遍历。

【输入样例】

5
5 7 1 2 10

【输出样例】

145
3 1 2 4 5

【提示】

数据范围与提示：

对于 100% 的数据，n<30,b<100，结果不超过 4×109 。

【来源】

无

　　这道题在信息奥赛一本通oj上被归类为树型动态规划，其实并不是，确实有树的数据结构要用到，但是更多需要的是区间动态规划的技巧。如果你不会区间动态规划，请戳这里学习区间动态规划。

　　首先，我们把这道题分成两个部分，分别是求最高加分和树的先序遍历，先来说最高加分怎么办：

　　先思考一下，题目中给出的顺序（中序遍历）有什么用？中序遍历的顺序是左子树 -> 根节点 -> 右子树，那么我们不妨枚举根节点的位置，那么根节点左边的就是左子树，右边的就是右子树，然后继续在左右子树中以同样的方法枚举根节点……直到分成叶子结点，返回该节点的分数就可以了。这样是什么，这不就是递归吗？所以我们这里采用记忆化搜索的形式来写。

　　那么我们就可以用f[i][j]来表示i到j区间内的最大加分，状态转移方程就很明了了：f[i][j]=max{f[i][k-1]+f[k+1][j]+a[i]}。

　　不过需要注意一点，可能会出现一些越界（其实是空树）情况，例如i>j时，记得返回1。

　　然后，我们来考虑怎么输出先序遍历，我们可以在执行上面的动态规划的过程中记录下一个root二维数组，root[i][j]表示i到j区间内选择的最优根节点编号，方便于输出先序遍历结果。最后只要按照先序遍历的顺序遍历就行了，碰到叶子节点时直接输出。

　　好了，代码如下：

#include<iostream>
using namespace std;
int f[1000][1000],a[1000],tree[1000],root[1000][1000],cnt,mid,n,ans;
int dp(int i,int j)//动态规划 
{
    if(i==j) return a[i];//碰到叶子结点直接返回 
    if(i>j) return 1;//注意空树（不存在左子树或右子树或都不存在）的情况 
    if(f[i][j]) return f[i][j];//记忆化 
    for(int k=i;k<=j;k++)
    {
        int x=dp(i,k-1)*dp(k+1,j)+a[k];//状态转移方程 
        if(f[i][j]<x)
        {
            f[i][j]=x;
            root[i][j]=k;//记录i~j区间的根节点 
        }
    }
    return f[i][j]; 
}
void print(int i,int j)
{
    if(i>j) return;//避免空树 
    if(i==j)//叶节点直接输出 
    {
        cout<<i<<" ";
        return;
    }
    cout<<root[i][j]<<" ";//根 
    print(i,root[i][j]-1);//左子树 
    print(root[i][j]+1,j);//右子树 
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    cout<<dp(1,n)<<endl;
    print(1,n);
    return 0;
}