[洛谷P1040]加分二叉树

题目

题目描述

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

输入样例

输出样例

题解

一道入门的区间dp,当然,根据写法不同你还可以把它归类为树形dp或者记忆化搜索,其实都无所谓啦。
作为一道入门题,我们完全可以“显然”地做出来,但是在这里还是想和大家回顾下动态规划以及区间动规。

Q:dp特点是什么?
A:dp把原问题视作若干个重叠的子问题的逐层递进,每个子问题的求解过程都会构成一个“阶段”,在完成一个阶段后,才会执行下一个阶段。
Q:dp要满足无后效性,什么叫无后效性?
A:已经求解的子问题不受后续阶段的影响。

有人觉得dp很抽象,那是因为没有一步一步来想,直接听别人的结论,我们在这里以这道题为例,一步一步来推导。

首先,我们要做的就是设计状态,其实就是设计dp数组的含义,它要满足无后效性。
关注这个 左子树*右子树+根 我只要知道左子树分数和右子树分数和根的分数(已给出),不就可以了吗?管他子树长什么样!
所以,我们\(f\)数组存的就是最大分数,怎么存呢?
我们发现:子树是一个或多个节点的集合。
那么我们可不可以开一个\(f[i][j]\)来表示节点i到节点j成树的最大加分呢?可以先保留这个想法(毕竟暂时也想不到更好的了)。

如果这样话,我们就来设计状态转移方程。
按照刚刚的设计来说的话,我们的答案就是\(f[1][n]\)了,那么我们可以从小的子树开始,也就是len,区间长度。有了区间长度我们就要枚举区间起点,i为区间起点,然后就可以算出区间终点j。
通过加分二叉树的式子我们可以知道,二叉树的分取决于谁是根,于是我们就在区间内枚举根k。
特别的,\(f[i][i]=a[i]\)其中a[i]为第i个节点的分数。
因为是要求最大值,所以我们就可以设计出
f[i][j]=MAX(f[i][k-1]*f[k+1][j]+f[k][k])
于是乎,我们就自己设计出了一个dp过程,因为是顺着来的,所以很少有不成立的。

至于输出前序遍历,我们再设计一个状态\(root[i][j]\)来表示节点i到节点j成树的最大加分所选的根节点。
所以我们按照\(根->左->右\)的顺序递归输出即可。

代码

发表评论

电子邮件地址不会被公开。 必填项已用*标注