AcWing 479. 加分二叉树

题目传送门

一、算法思路

(区间DP,二叉树的遍历) \(O(n^3)\)

状态表示：f[i][j] 表示中序遍历是 w[i ~ j] 的所有二叉树的得分的最大值。

状态计算：f[i][j] = max(f[i][k - 1] * f[k + 1][j] + w[k])，即将f[i][j]表示的二叉树集合按根节点分类，则根节点在 k 时的最大得分即为 f[i][k - 1] * f[k + 1][j] + w[k]，则f[i][j]即为遍历 k 所取到的最大值。

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

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

二、实现代码

#include 

using namespace std;

//区间DP问题怎么记录方案
//加分二叉树

const int N = 50;

int n;
int w[N];        //权值
int f[N][N];    //区间DP数组
int g[N][N];    //记录i,j区间内的最大得分，是在k这个节点为根的情况下获得的
//前序遍历输出
void dfs(int l, int r) {
    if (l > r) return;
    int k = g[l][r];
    printf("%d ", k);
    dfs(l, k - 1);
    dfs(k + 1, r);
}

int main() {
    //优化输入
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> 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]; //左子树为空，返回1
                int right = k == r ? 1 : f[k + 1][r];//右子树为空，返回1
                //计算得分
                int score = left * right + w[k];
                if (l == r) score = w[k];//如果左子树为空，右子树也为空
                //因为需要记录第一个取得最大的值(字典序)，不能使用Max
                if (f[l][r] < score) {
                    f[l][r] = score;
                    g[l][r] = k;    //记录l~r区间的最大得分是由哪个根节点k转化而来
                }
            }
        }
    //输出
    printf("%d\n", f[1][n]);
    //利用递归，输出路径
    dfs(1, n);
    return 0;
}