题目描述
设一个\(n\)个节点的二叉树\(tree\)的中序遍历为\((1,2,3,…,n)\),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整数),记第i个节点的分数为\(d_i\),\(tree\)及它的每个子树都有一个加分,任一棵子树\(subtree\)(也包含\(tree\)本身)的加分计算方法如下:
\(subtree\)的左子树的加分\(\times subtree\)的右子树的加分\(+ subtree\)的根的分数。
若某个子树为空,规定其加分为11,叶子的加分就是叶节点本身的分数。不考虑它的空子树。
试求一棵符合中序遍历为\((1,2,3,…,n)\)且加分最高的二叉树\(tree\)。要求输出;
(1)\(tree\)的最高加分
(2)\(tree\)的前序遍历
Links
Solution
很明显的,题目给出的输入是一个中序遍历,因此一个节点的左子树必定在序列中它的左边,一个节点的右子树必定在序列中它的右边,因此可以通过枚举中间节点进行记忆化搜索,在输出部分,因为题目要求输出前序遍历,那么使用一个数组在每次发生更新时存储区间\([left,right]\)的父亲节点,输出时,先输出当前区间的父节点,然后递归的输出左子树和右子树即可
Code
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long LL;
typedef pair <int, int> pii;
template <typename T> inline T read(){
T sum=0;
int fl=1,ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') fl=-1;
for(;isdigit(ch);ch=getchar()) sum=(sum<<3)+(sum<<1)+ch-'0';
return sum*fl;
}
const int maxn=50+5;
int n;
int a[maxn][maxn];
int v[maxn];
int root[maxn][maxn];
int dfs(int l,int r){
if(a[l][r]>0) return a[l][r]; //记忆化
if(l==r) return v[l]; //当前查找到的为单点,直接返回
if(r<l) return 1; //没有子树,加分为1
for(int i=l;i<=r;i++){
int tmp=dfs(l,i-1)*dfs(i+1,r)+a[i][i];
if(tmp>a[l][r]){
a[l][r]=tmp;
root[l][r]=i;
}
}
return a[l][r];
}
void print(int l,int r){
if(r<l) return;
if(l==r){
printf("%d ",l);
return;
}
printf("%d ",root[l][r]); //先输出根
print(l,root[l][r]-1);//再输出左子树
print(root[l][r]+1,r);//最后输出右子树
}
int main(){
n=read<int>();
for(int i=1;i<=n;i++){
v[i]=read<int>();
a[i][i]=v[i];
}
printf("%d\n",dfs(1,n));
print(1,n);
return 0;
}