「NOIp2003」加分二叉树-记忆化搜索 or 动态规划

题目描述

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

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

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

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

(1)$tree​$的最高加分

(2)$tree​$的前序遍历

Luogu P1040

Solution

很明显的,题目给出的输入是一个中序遍历,因此一个节点的左子树必定在序列中它的左边,一个节点的右子树必定在序列中它的右边,因此可以通过枚举中间节点进行记忆化搜索/DP,在输出部分,因为题目要求输出前序遍历,那么使用一个数组在每次发生更新时存储区间$[left,right]$的父亲节点,输出时,先输出当前区间的父节点,然后递归的输出左子树和右子树即可

Code

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#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;
}