[NOIP2003 提高组] 加分二叉树
题目描述
设一个 个节点的二叉树
的中序遍历为
，其中数字
为节点编号。每个节点都有一个分数（均为正整数），记第
个节点的分数为
，
及它的每个子树都有一个加分，任一棵子树
（也包含
本身）的加分计算方法如下：
的左子树的加分
的右子树的加分
的根的分数。
若某个子树为空，规定其加分为 ，叶子的加分就是叶节点本身的分数。不考虑它的空子树。
试求一棵符合中序遍历为 且加分最高的二叉树
。要求输出
的最高加分。
输入格式
第 行
个整数
，为节点个数。
第 行
个用空格隔开的整数，为每个节点的分数
输出格式
第 行
个整数，为最高加分（$ Ans \le 4,000,000,000$）。
第 行
个用空格隔开的整数，为该树的前序遍历。
样例 #1
样例输入 #1
5
5 7 1 2 10样例输出 #1
145
3 1 2 4 5提示
数据规模与约定
对于全部的测试点，保证 ，节点的分数是小于
的正整数，答案不超过
。
#include<iostream>
#include<cmath>
#include<cstdio>
int n;
int f[35];
int s[35][35],p[35][35];
using namespace std;
int dfs(int l,int r)
{
if(l>r)return 1;//如果交叉则说明此结点无儿子，则默认为权值为1
if(l==r){s[l][r]=l;return f[l];}//如果正好只有一个结点的，那么直接返回该结点的值
if(p[l][r])return p[l][r];//①记忆化搜索
int ans=0,num;
for(int k=l;k<=r;k++)//枚举子层次的根节点
{
int t=dfs(l,k-1)*dfs(k+1,r)+f[k];
if(t>ans)
{
ans=t;//取得以此根为结点的权值的最优
num=k;// 标记以在l~r这些子结点之中以num为根是最优结果
}
}
s[l][r]=num;//记忆 num
return p[l][r]=ans;//记忆化
}
void zhao(int l,int r)
{
if(l>r)return;
cout<<s[l][r]<<" ";//输出根
zhao(l,s[l][r]-1);//递归输出左结点
zhao(s[l][r]+1,r);//递归输出右结点
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>f[i];
cout<<dfs(1,n)<<endl;
zhao(1,n);
return 0;
}