题目描述
就是一棵树的中序遍历,然后让我们求这颗树的最大加分,也就是求根节点的最大加分(未说根节点是哪个)
加分规则如下:
(1)如果当前节点是叶节点,那么他的加分就是初始给的分数w[i]
(2)如果当前节点是空树,或者说不存在,那么他的加分固定为1
(3)如果当前节点是非叶非空节点,那么他的加分就是左子树加分*右子树加分+自己的分数w[i]
最终我们需要输出根节点的最大加分,再输出其前序遍历,如果存在多种相同最大加分(也就意味着有多颗二叉树)
输出字典序最小的那棵二叉树的前序遍历
输入样例
5
5 7 1 2 10
输出样例
145(二叉树的最大加分)
3 1 2 4 5(最优解二叉树的前序遍历)
实现思路:
这个题目一开始就告诉我们中序序列就是按照1 2 3 4 5 ....的递增顺序 让我们就是利用中序遍历的特点,
假如说最优解情况的1-5的根节点是k 那么1 到 k-1就是其左子树 k+1 到 5 就是其右子树
题目说每个节点有加分的规则 我们要求的就是最终的那颗树的加分!
那我们具体咋实现呢?
我们可以枚举根节点,找出其最优解即可,但是很明显我不可能直接求出1到n的根节点的最大加分,我肯定是需要其
左右子树的加分情况,说到这里就已经非常非常容易想到区间dp了。
设:int f[N][N];//计算答案 f[i][j]表示i-j能表示的所有二叉树情况的集合 属性是最大值
所以说:
一开始我们直接枚举区间长度,长度为1时需要特判一下,因为此时的节点是叶节点 所以其f[i][j]=w[i];
其他情况直接求就好了,具体的状态转移方程如下,还有一点就是我们需要求出前序遍历,那我们完全可以再开
一个数组g[N][N],g[i][j]表示最优解二叉树i到j的根节点是什么,还有就是因为要求字典序最小,所以我们刚
开始就从小到大枚举,并且保证只更新最靠前的最大加分值!
状态转移方程:
(1)当前根节点k就是叶节点
f[i][j]=w[k]; 叶节点特殊考虑就是w[i]
(2)当前根节点k不是叶节点
f[i][j]=max(f[i][j],f[i][k-1]*f[k+1][j]+w[k])
参考文献
y总讲课思路(doge)
C++ 代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=35;
int w[N];//记录每个点的权值
int f[N][N];//计算答案 f[i][j]表示i-j能表示的所有二叉树情况的集合 属性是最大值
int g[N][N];//这个是用来记录根节点的比如说 i-j 二叉树的根节点是k 那么g[i][j]=k
int n;
void init()
{
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
f[i][j]=1;//一开始全部初始化为1 这样就不需要特判空子树了
}
void dfs(int l,int r)
{
cout<<g[l][r]<<" ";
if(l<=g[l][r]-1)dfs(l,g[l][r]-1);
if(r>=g[l][r]+1)dfs(g[l][r]+1,r);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>w[i];
init();
for(int len=1;len<=n;len++)
for(int i=1;i+len-1<=n;i++)
{
int l=i,r=i+len-1;
if(l==r){
f[l][r]=w[l];
g[l][r]=l;
continue;
}//说明是叶节点 叶节点的
for(int k=l;k<=r;k++)//保证每个点都有可能当跟节点
{
if(f[l][r]<f[l][k-1]*f[k+1][r]+w[k]){
g[l][r]=k;
f[l][r]=f[l][k-1]*f[k+1][r]+w[k];
}
}
}
cout<<f[1][n]<<endl;
dfs(1,n);
return 0;
}