洛谷P1040 加分二叉树

洛谷P1040 加分二叉树

题意：

按中序遍历的顺序给出一棵二叉树各个节点的值，求出这棵树的最大得分，以及此时的前序遍历
记分规则如下：

1. 有两个子树：两个子树分数的乘积加上根的值
2. 有一个子树：该子树的分数加上根的值
3. 没有子树(叶子节点)：该节点的值

分析：

输入数据是二叉树的中序遍历，那么就要考虑中序遍历的特点
在中序遍历中，若确定一个点为根节点，那么这个点左侧的点一定为该根节点左子树上的节点，这个点右侧的点一定为该根节点右子树上的节点
因此这个题的关键就是确定某一区间(子树)的根节点
所以很容想到区间DP
状态转移方程: $dp\left[i\right]\left[j\right]=max\left(dp\right[i\left]\right[k-1]\ast dp[k+1\left]\right[j]+dp[k\left]\right[k],dp[i\left]\right[j\left]\right)$dp[i][j]=max(dp[i][k−1]∗dp[k+1][j]+dp[k][k],dp[i][j])

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 35;
LL dp[maxn][maxn] = {0};
int root[maxn][maxn];
void preorder(int l, int r)
{
    if (l > r)
        return;
    printf("%d ", root[l][r]);
    preorder(l, root[l][r] - 1);
    preorder(root[l][r] + 1, r);
}
int main(int argc, char const *argv[])
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%lld", &dp[i][i]);
        dp[i][i - 1] = 1;
        dp[i + 1][i] = 1;
        root[i][i] = i;
    }
    //错误的DP，我一开始没多想，就这样写了，然后发现要求dp[i][j]时dp[k+1][j]还是未知的...
    // for (int i = 1; i <= n; ++i)
    // {
    // for (int j = i; j <= n; ++j)
    // {
    // for (int k = i; k <= j; ++k)
    // {
    // if (dp[i][j] < dp[i][k - 1] * dp[k + 1][j] + dp[k][k])
    // {
    // dp[i][j] = dp[i][k - 1] * dp[k + 1][j] + dp[k][k];
    // root[i][j] = k;
    // }
    // }
    // }
    // }
	
	//正确的DP，上面的dp之所以错就是因为要求更大的区间时小区间还未确定，所以要以区间长度作为第一层循环
    for (int l = 2; l <= n; ++l)
    {
        for (int i = 1; i <= n - l + 1; ++i)
        {
            for (int j = i; j <= i + l - 1; ++j)
            {
                if (dp[i][i + l - 1] < dp[i][j - 1] * dp[j + 1][i + l - 1] + dp[j][j])
                {
                    dp[i][i + l - 1] = dp[i][j - 1] * dp[j + 1][i + l - 1] + dp[j][j];
                    root[i][i + l - 1] = j;
                    // cout << "dp[" << i << "][" << i + l - 1 << "]=" << dp[i][i + l - 1] << endl;
                }
            }
        }
    }

    printf("%lld\n", dp[1][n]);
    preorder(1, n);
    printf("\n");
    return 0;
}