CJOJ 1010【NOIP2003】加分二叉树 / Luogu 1040 加分二叉树（树型动态规划）

Description

设 一个 n 个节点的二叉树 tree 的中序遍历为（ 1,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 的前序遍历

Input

第 1 行：一个整数 n （ n ＜ 30 ），为节点个数。

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

Output

第 1 行：一个整数，为最高加分（结果不会超过 4,000,000,000 ）。

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

Sample Input

5

5 7 1 2 10

Sample Output

145

3 1 2 4 5

Http

CJOJ:http://oj.changjun.com.cn/problem/detail/pid/1010

Luogu:https://www.luogu.org/problem/show?pid=1040

CodeVS:http://codevs.cn/problem/1090/

Source

树型动态规划

解决思路

因为题目给出的是中序遍历，所以有任意一棵子树的中序遍历一定是在一段里面的，我么令F[i][j]表示从i到j的最大加分，用Mayuri[i][j]表示i,j能得到最大加分的根节点。

那么我们可以枚举[i,j]之间的一个点k为根节点，得到状态转移方程F[i][j]=max(F[i][k-1]*F[k+1][j]+Value[k])同时更新Mayuri[i][j]，最后的结果就是F[1][n]。

最后输出，这里我们采用递归调用的方法，在主函数里调用Outp(1,n)，对于Outp(i,j)来说，我们调用Outp(i,Mayuri[i]-1) Outp(Mayuri[i]+1,j)，分别按照前序遍历输出。

需要注意的是各个变量的初始值赋值，具体请看代码。

代码

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxsize=100;

const int inf=2147483647;

int n;

long long Node[maxsize];//存放每个点的权值

long long F[maxsize][maxsize];//F[i][j]如题解中所示

int Mayuri[maxsize][maxsize];//Mayuri[i][j]表示i,j这棵树的根节点

void Outp(int l,int r);

int main()

{

    memset(F,0,sizeof(F));

    cin>>n;

    for (int i=1;i<=n;i++)

        cin>>Node[i];

    for (int i=1;i<=n;i++)

        F[i][i-1]=1;//F[][]的初始化

    for (int i=1;i<=n;i++)

    {

        F[i][i]=Node[i];//F的初始化

        Mayuri[i][i]=i;//Mayuri的初始化

    }

    for (int i=n;i>=1;i--)

    {

        for (int j=i+1;j<=n;j++)

        {

            for (int k=i;k<=j;k++)

                if (F[i][k-1]*F[k+1][j]+Node[k]>F[i][j])

                {

                    F[i][j]=F[i][k-1]*F[k+1][j]+Node[k];

                    Mayuri[i][j]=k;

                    //cout<<"Update : "<<i<<' '<<j<<' '<<k<<' '<<F[i][j]<<endl;

                }

        }

    }

    cout<<F[1][n]<<endl;

    Outp(1,n);//递归输出前序遍历

    cout<<endl;

    return 0;

}

void Outp(int l,int r)

{

    if (l>r)

        return;

    cout<<Mayuri[l][r]<<' ';//因为是前序遍历，所以先输出根节点

    if (l==r)

        return;

    Outp(l,Mayuri[l][r]-1);//递归调用

    Outp(Mayuri[l][r]+1,r);

    return;

}