<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

设一个 $n$ 个节点的二叉树 tree 的中序遍历为（$1,2,3,…,n$），其中数字 $1,2,3,…,n$ 为节点编号。

每个节点都有一个分数（均为正整数），记第 $i$ 个节点的分数为 $d_i$，tree 及它的每个子树都有一个加分，任一棵子树 subtree（也包含 tree 本身）的加分计算方法如下：     

subtree的左子树的加分 $×$ subtree的右子树的加分 $＋$ subtree的根的分数 

若某个子树为空，规定其加分为 $1$。

叶子的加分就是叶节点本身的分数，不考虑它的空子树。

试求一棵符合中序遍历为（$1,2,3,…,n$）且加分最高的二叉树 tree。

要求输出： 

（1）tree的最高加分 

（2）tree的前序遍历

输入格式

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

第 $2$ 行：$n$ 个用空格隔开的整数，为每个节点的分数（$0<$分数$<100$）。

输出格式

第 $1$ 行：一个整数，为最高加分（结果不会超过int范围）。     

第 $2$ 行：$n$ 个用空格隔开的整数，为该树的前序遍历。如果存在多种方案，则输出字典序最小的方案。

数据范围

$n < 30$

输入样例：

5
5 7 1 2 10

输出样例：

145
3 1 2 4 5

思路

闫氏$\text{DP}$分析法：
状态表示：$f_{i,j}$

• 集合：中序遍历为$i\sim j$所组成加分二叉树的最大分数
• 属性：$\max$

状态计算：

• 假设分界点是$k$，如果$k=i$，那么分数就是$1\times f_{k + 1,j}+a_k$
• 如果$k=j$那么分数就是$f_{i,k-1}\times 1 + a_k$
• 如果$i < k < j$，分数就是$f_{i,k-1}\times f_{k+1,j} + a_k$
• 所以状态转移方程就是$f_{i,j}=\underset{k\in [i+1,j-1]}\max{\{f_{i+1,j}+a_k,f_{i,j-1}+a_k,f_{i,k - 1} + f_{k + 1,j} + a_k\}}$

代码

#include <iostream>
using namespace std;
const int N = 40;
int n;
int a[N];
int f[N][N];
int root[N][N];
void dfs (int l,int r) {
    if (l > r) return ;
    int k = root[l][r];
    cout << k << ' ';
    dfs (l,k - 1),dfs (k + 1,r);
}
int main () {
    cin >> n;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
        f[i][i] = a[i],root[i][i] = i;
    }
    for (int len = 2;len <= n;len++) {
        for (int i = 1;i + len - 1 <= n;i++) {
            int j = i + len - 1;
            for (int k = i;k <= j;k++) {
                int left = k == i ? 1 : f[i][k - 1],right = k == j ? 1 : f[k + 1][j];
                int ans = left * right + a[k];
                if (ans > f[i][j]) {
                    f[i][j] = ans;
                    root[i][j] = k;
                }
            }
        }
    }
    cout << f[1][n] << endl;
    dfs (1,n);
    cout << endl;
    return 0;
}