中序遍历二叉树中的最小开销

题目来源于美团2021校招练习第10套第4题

小团有一个由N个节点组成的二叉树,每个节点有一个权值。定义二叉树每条边的开销为其两端节点权值的乘积,二叉树的总开销即每条边的开销之和。小团按照二叉树的中序遍历依次记录下每个节点的权值,即他记录下了N个数,第i个数表示位于中序遍历第i个位置的节点的权值。之后由于某种原因,小团遗忘了二叉树的具体结构。在所有可能的二叉树中,总开销最小的二叉树被称为最优二叉树。现在,小团请小美求出最优二叉树的总开销。

  • 输入描述

      第一行输入一个整数N(1<=N<=300),表示二叉树的节点数。
      第二行输入N个由空格隔开的整数,表示按中序遍历记录下的各个节点的权值,
      所有权值均为不超过1000的正整数。
    
  • 输出描述

      输出一个整数,表示最优二叉树的总开销。
    
  • 示例1

    输入

      5
      7 6 5 1 3
    

    输出

      45
    

    说明

      最优二叉树如图所示,总开销为7*1+6*5+5*1+1*3=45。
    

题意:在以给出序列为中序序列的所有二叉树中,找出最小的开销值。开销值为二叉树上所有的边两边节点的权重乘积之和。

题解:这道题的关键在于根据中序遍历的特点发现下面这个等式。当指定一个结点i为根节点时,i左边的都是左子树上的内容,i右边的都是右子树上的内容,因此开销为左子树上的开销和加上右子树上的开销和。进一步地,如果我们只考虑[l,r]上的位置,选取[l,r]上的某一点i为根节点,那[l,r]上的开销可以表示为foo(l, i) + foo(i, r) + i与这个区间外的父亲的权重乘积之和。因此,我们只需要递归的枚举从1到n的所有位置为根节点,用dp[i][j][root]表示在[i,j]序列中,以root为父亲节点的最小权值。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int arr[305];
int dp[305][305][305];
int foo (int l, int r, int root) {
if (l > r) return 0;
if (dp[l][r][root] != -1) return dp[l][r][root];
int maxn = 0x7fffffff;
for (int i = l; i <= r; ++i) {
int left = foo(l, i - 1, i);
int right = foo(i + 1, r, i);
maxn = min(maxn, left + right + arr[i] * arr[root]);
}
dp[l][r][root] = maxn;
return dp[l][r][root];
}
int main()
{
int n;
scanf("%d", &n);
memset(dp, -1, sizeof(dp));
for (int i = 1; i <= n; ++i) {
scanf("%d", arr + i);
}
arr[0] = 0;
int res = foo(1, n, 0);
printf("%d\n", res);
return 0;

}