首页 > 其他 > 详细

加分二叉树

时间:2018-08-20 13:36:56      阅读:153      评论:0      收藏:0      [点我收藏+]

 

试题描述

    设一个 n 个节点的二叉树 tree 的中序遍历为 (1,2,3,?,n),其中数字 1,2,3,? 为节点编号。每个节点都有一个分数(均为正整数),记第 i 个节点的分数为 di?? ,tree 及它的每个子树都有一个加分,任一棵子树 subtree(也包含 tree 本身)的加分计算方法如下:记 subtree 的左子树加分为 l,右子树加分为 r,subtree 的根的分数为 a,则 subtree 的加分为:l×r+a 若某个子树为空,规定其加分为 1,叶子的加分就是叶节点本身的分数。不考虑它的空子树。试求一棵符合中序遍历为 (1,2,3,?,n) 且加分最高的二叉树 tree。

    要求输出:tree 的最高加分和 tree 的前序遍历。

输入
第一行一个整数 n 表示节点个数;第二行 n 个空格隔开的整数,表示各节点的分数。
输出
第一行一个整数,为最高加分 b;第二行包含 n 个整数,两两之间用一个空格分隔,为该树的前序遍历。
输入示例
5
5 7 1 2 10
输出示例
145
3 1 2 4 5
其他说明
数据范围:对于 100% 的数据,n<30,b<100,结果不超过 4×10^?9?? 。

 看注释

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
inline int rd()
{
    int x=0,f=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch==-) f=-1;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-0;
    return x*f;
}
inline void write(int x)
{
    if(x<0) putchar(-),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+0);
    return ;
}
int s[100006],f[1006][1006];
int set[1006][1006];
void dfs(int l,int r)
{
    if(l>r) return ;
    printf(" %d",set[l][r]);
    dfs(l,set[l][r]-1);
    dfs(set[l][r]+1,r);
}
int main()
{
    int n;
    n=rd();
    for(int i=1;i<=n;i++)
    {
        f[i][i]=rd();//输入可以简化,但是不必要 
        f[i][i-1]=1;//读题一定要仔细,非空子树加分为1 (调了半天) 
        set[i][i]=i;//每个节点分割点为自己 
    }
    /*
       划重点!!!
       这道题乍一眼看上去是树形DP
       但实际上多读几遍题就会发现这是区间DP裸题
       “记 subtree 的左子树加分为 l,右子树加分为 r,subtree 的根的分数为 a,则 subtree 的加分为:l×r+a” 
       这句话生动形象的刻画了这道题区间DP的精髓所在 
       由此推出转移方程
       dp[i][j]=max(dp[i][j],dp[i][k-1]+dp[k+1][j]+dis[k]);
       dp[i][j]表示从节点i到节点j的最大加分
       特别的是因为是树结构,所以k-1和k+1,不能包含根节点 
    */
    for(int l=1;l<=n;l++)
    {
        for(int i=1;i<=n-l;i++)
        {
            int j=i+l;
            for(int k=i;k<=j;k++)
            {
                if(f[i][j]<f[i][k-1]*f[k+1][j]+f[k][k])
                {
                    f[i][j]=f[i][k-1]*f[k+1][j]+f[k][k];
                    set[i][j]=k;//存根节点 
                }
            }
        }
    }
    printf("%d\n",f[1][n]);
    printf("%d",set[1][n]);//输出,因为是先序遍历,所以要用到dfs,注意输出格式有没有某位的空格 
    dfs(1,set[1][n]-1);
    dfs(set[1][n]+1,n);
    return 0;
}

最后喜欢的话不如来推荐,评论,关注三连。

不喜欢的话也昧着良心推荐一下吧!!!!

加分二叉树

原文:https://www.cnblogs.com/WWHHTT/p/9505034.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!