P1040加分二叉树（区间DP

噬月 · 2020-02-15 12:25:19 · 题解

P1040加分二叉树

猜想 ：此题可以用DP来做。

首先我们想，符合条件的二叉树是加分最高的二叉树，它的总分依题意得 总分 = 左子树分数 * 右子树分数 + 根节点分数 ，不难看出，欲使总分最高，左右子树的分数应当也分别取最高。 而子树的最高分怎么求呢？自然也是 子树总分 = 子树左子树分数 * 子树右子树分数 + 子树根节点分数 由此我们得到此题具有最优子结构性质。

又，分数计算公式只和左子树分数，右子树分数和根节点分数有关，与如何得到这两个子树分数的方法和路径无关，易得此题的解具有无后效性。

故猜想可行。

设计状态 ：设计DP数组的含义，使其满足无后效性。

题目中给出的节点序号根据二叉树的中序遍历排列，可以想见，任取两个下标i,j,(i<j)，可以表示从节点i到节点j所构成的子树的最高加分（由无后效性可知，当区间之外还有子树时，此最高分叠加了区间[i, j]之外的节点的最高分）。并设k(i \le k \le j)为该子树的根节点，通过枚举根的不同位置来取得不同的左右子树和根节点分数，进而得出最大值。

特别地，我们约定①，当下标相等时，f_{x, x} 的初始值为序号为x的节点的初始分数。

由此我们写出 状态转移方程 ：

因为题目要求前序遍历输出，我们再使用一个二维数组root来记录从节点i到节点j的最高分子树的根。

代码

#include<iostream>
#include<cstdio>

long long n;
long long f[50][50], root[50][50];
//f[i][j] showes the max scroe from i to j
//f[i][j] = max(f[i][k - 1] * f[k + 1][j] + f[k][k])
//root[i][j] showes the root of the max scroe picked

using namespace std;

void print(long long l, long long r) {
    if (l > r) {
        return;
    }
    printf("%lld ", root[l][r]);
    if (l == r) {
        return;
    }
    print(l, root[l][r] - 1);
    print(root[l][r] + 1, r);
}

int main() {

    cin >> n;
    for (int i = 1; i <= n; ++ i ) {

        cin >> f[i][i];//node
        f[i][i - 1] = 1;//left subtree error handling②
        f[i + 1][i] = 1;//right subtree error handling
        root[i][i] = i;
    }

    for (int range = 1; range <= n; ++ range ) {
    //enumerate length of range, 
        for (int i = 1; i + range <= n; ++ i ) {
    //then enumerate the start point of range
            int j = i  + range;//end point

            //enumerate possible root from start point by default
            for (int k = i ; k <= j; ++ k ) {

                if (f[i][j] < f[i][k - 1] * f[k + 1][j] + f[k][k]) {

                    f[i][j] = f[i][k - 1] * f[k + 1][j] + f[k][k];
                    root[i][j] = k;
                }
            }
        }
    }

    cout << f[1][n] << endl;
    print(1, n);

    return 0;
}

注 ：

①：按照约定之前的定义思路，下标相等时，由无后效性可知，当节点有子树时，此f[x][x]叠加了子树的最高分。而我们希望它表示序号为x的节点的初始分数，因此称为约定。并且我们强调初始值，因为之后是有可能会更新成更大值的。

②：当k取i时，会出现f[i][k - 1]这种下标相反的情况；k取j时则在另一端f[k + 1][j]出现同样的状况。此时的根节点k超出了区间的处理范围；映射到图上，则可以认为是一种左（右）子树为空的状态。由于题目给出空子树默认分数为1，我们令f[i][k - 1] = 1。

关于等号的讨论：

if (f[i][j] < f[i][k - 1] * f[k + 1][j] + f[k][k]) {

    f[i][j] = f[i][k - 1] * f[k + 1][j] + f[k][k];
    root[i][j] = k;
}

其中的不等号改为等号是否有影响？

修改之后对于同一组输入，输出最高分不变，但前序遍历发生了改变：

输入：
5
5 7 1 2 10
输出（修改前）：
145
3 1 2 4 5
输出（修改后）：
145
3 2 1 5 4

若画出树，可以发现是末端度为1的单叶节点和其叶节点发生了互换；

使用另一组数据：

10
5 4 8 9 19 2 1 40 20 22

可以得到同样的实验结果（节点互换）。

结合枚举根节点的思路，我们可以发现，枚举根的过程反映到图上是在枚举不同的树型。

关于边界的讨论：

上述第一组数据生成的最高分树是：

     3
    / \
   1    4
    \   \
    2    5

现在我们假设枚举过程中到了这样一个情形：