算法知识点: 区间DP，二叉树的遍历

复杂度：

解题思路：

状态表示： 表示中序遍历是 的所有二叉树的得分的最大值。
状态计算：，即将表示的二叉树集合按根节点分类，则根节点在 时的最大得分即为 ，则即为遍历 所取到的最大值。

在计算每个状态的过程中，记录每个区间的最大值所对应的根节点编号。

那么最后就可以通过DFS求出最大加分二叉树的前序遍历了。

C++ 代码： 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
 
typedef pair <int, int> PII; const int N = 50;
 
int n;
int w[N];
unsigned f[N][N];
int root[N][N];
 
void dfs(int l, int r)
{
    if (l > r) return;
 
    int k = root[l][r];
    printf("%d ", k, f[l][r]);
    dfs(l, k - 1);
    dfs(k + 1, r);
}
 
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
    for (int len = 1; len <= n; len++)
        for (int l = 1; l + len - 1 <= n; l++)
        {
            int r = l + len - 1;
 
            for (int k = l; k <= r; k++)
            {
                int left = k == l ? 1 : f[l][k - 1];
                int right = k == r ? 1 : f[k + 1][r];
                int score = left *right + w[k];
                if (l == r) score = w[k];
                if (f[l][r] < score)
                {
                    f[l][r] = score;
                    root[l][r] = k;
                }
            }
        }
 
    printf("%d\n", f[1][n]);
    dfs(1, n);
    puts("");
 
    return 0;
}


另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
报名优惠券：DCYxdCJ