[NOIP2003 提高组] 加分二叉树

题目描述

设一个 $n$ 个节点的二叉树 $\text{tree}$ 的中序遍历为$(1,2,3,\ldots,n)$，其中数字 $1,2,3,\ldots,n$ 为节点编号。每个节点都有一个分数（均为正整数），记第 $i$ 个节点的分数为 $d_i$，$\text{tree}$ 及它的每个子树都有一个加分，任一棵子树 $\text{subtree}$（也包含 $\text{tree}$ 本身）的加分计算方法如下：

$\text{subtree}$ 的左子树的加分 $\times$ $\text{subtree}$ 的右子树的加分 $+$ $\text{subtree}$ 的根的分数。

若某个子树为空，规定其加分为 $1$，叶子的加分就是叶节点本身的分数。不考虑它的空子树。

试求一棵符合中序遍历为 $(1,2,3,\ldots,n)$ 且加分最高的二叉树 $\text{tree}$。要求输出

  1. $\text{tree}$ 的最高加分。

  2. $\text{tree}$ 的前序遍历。

输入格式

第 $1$ 行 $1$ 个整数 $n$，为节点个数。

第 $2$ 行 $n$ 个用空格隔开的整数，为每个节点的分数

输出格式

第 $1$ 行 $1$ 个整数，为最高加分（$ Ans \le 4,000,000,000$）。

第 $2$ 行 $n$ 个用空格隔开的整数，为该树的前序遍历。

样例 #1

样例输入 #1

1
2
5
5 7 1 2 10

样例输出 #1

1
2
145
3 1 2 4 5

提示

数据规模与约定

对于全部的测试点，保证 $1 \leq n< 30$，节点的分数是小于 $100$ 的正整数，答案不超过 $4 \times 10^9$。

题解

题目解析

​ 听dalao说这个题是区间dp的题,但是我没有学过= =.我从B站看了个视频,发现这个其实还有其他做法:dfs+记忆化搜索.

​ 这道题输入的是树的中序遍历,由于中序遍历中是左->根->右的遍历方法,我们并不确定哪个位置是根,所以我们需要去一个一个枚举哪个节点是某个区间的根.然后根据遍历的节点加分最大值来保存到dp数组中并保存根的位置到rt数组中.

​ 这是加分最大输出方法,接下来处理前序输出.具体方法用rt数组,然后递归输出就好了.

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <cstring>
typedef long long ll;
using namespace std;

int a[40],rt[40][40],n;//rt为在l->r中哪个是根节点
ll dp[40][40];

ll dfs(int l,int r){
    if(l > r) return 1;//题目中已经提到:若某个子树为空，规定其加分为 1
    if(l == r){rt[l][r] = l; return a[l];}//l==r时,说明这个位置正好是叶子节点
    if(dp[l][r] != -1) return dp[l][r];//记忆化搜索
    for(int i=l;i<=r;i++){
        ll temp = dfs(l,i-1) * dfs(i+1,r) + a[i];//题目中说了
        if(temp > dp[l][r]){//如果在l->r以i为根的时候得到的加分值大于原来l->r的加分值
            dp[l][r] = temp;//l->r的最大加分为temp
            rt[l][r] = i;//l->r的根节点为i
        }
    }
    return dp[l][r];//返回l->r的最大加分值
}

void putout(int l,int r){//根左右输出
    if(l > r) return;
    cout << rt[l][r] << " ";
    putout(l,rt[l][r]-1);
    putout(rt[l][r]+1,r);
}

int main(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    memset(dp,-1,sizeof(dp));
    cout << dfs(1,n) << endl;
    putout(1,n);
    return 0;
}