106. [NOIP2003] 加分二叉树

★☆ 输入文件：jfecs.in 输出文件：jfecs.out 简单对比
时间限制：1 s 内存限制：128 MB

【问题描述】

设一个 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 个用空格隔开的整数，为该树的前序遍历。

【输入样例】

5
5 7 1 2 10

【输出样例】

145
3 1 2 4 5

思路：区间DP，和那道石子合并有点类似。

f[i][j]记录区间i到j的最大值，root[i][j]记录此时的根是几。

那么状态转移方程就可以很轻易地求出来：f[i][j]=max(f[i][j],f[i][k-1]*f[k+1][j]+num[k])，顺便记录root[i][j]=k；

最后再跑一边先序遍历即可。

错因：数组初始化应该从0开始。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define MAXN 31

using namespace std;

long long f[MAXN][MAXN];

int n,num[MAXN],root[MAXN][MAXN];

void dfs(int l,int r){

    if(l>r)    return ;

    cout<<root[l][r]<<" ";

    dfs(l,root[l][r]-);

    dfs(root[l][r]+,r);

}

int main(){

    freopen("jfecs.in","r",stdin);

    freopen("jfecs.out","w",stdout);

    scanf("%d",&n);

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

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

            f[i][j]=;

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

        scanf("%d",&num[i]);

        f[i][i]=num[i];

        root[i][i]=i;

    }

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

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

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

                if(f[i][k-]*f[k+][j]+num[k]>f[i][j]){

                    root[i][j]=k;

                    f[i][j]=f[i][k-]*f[k+][j]+num[k];

                }

    cout<<f[][n]<<endl;

    dfs(,n);

}

加分

cogs 106. [NOIP2003] 加分二叉树(区间DP)

106. [NOIP2003] 加分二叉树