P1040 加分二叉树 题解

洛谷 P1040 加分二叉树 【普及+/提高】 题解

首先分析题意，题目中说到中序遍历，我们知道对于一棵二叉树的中序遍历，一个结点在序列中对应的位置，它的左边都是这个结点的左子树，它的右边都是这个结点的右子树。
而题目中又说这个树的中序遍历是 (1,2,3,...,n) ，那么我们很容易能得到状态转移方程。设 (a[i]) 为第 (i) 个结点的分数 (f[l][r]) 表示在中序遍历中 ([l,r]) 的一段所对应的树能够获得的最大加分，则有

[f[l][r] = max_{lleq kleq r} f[l][k-1]*f[k+1][r]+a[k]. ]

属性	描述
枚举顺序	从 (r-l+1) （即区间长度）由大到小枚举。
初始化	(f[i][i] = a[i], 1leq ileq n\ f[i][i-1] = 1,1leq ileq n).
目标	(f[1][n])

实际上是一个区间dp。其中我们需要注意初始化的第二个条件。对于上面的dp方程，当 (k=l)时，原式右边为 (f[l][l-1] * f[l+1][r] + a[l])。这实际上是左子树为空的情况。根据题意，左子树空（但右子树不空）时，其加分算作 (1) 。因此要把所有的 (f[i][i-1],1leq ileq n) 都初始化为 1。
这是子任务1。子任务2怎么做呢？我们可以再设计一个 dp :
设 (p[l][r]) 表示在中序遍历中 ([l,r]) 的一段所对应的树中选择哪个结点作为根，能获得最大的加分。则不难发现，(k) 即为使 (f[l][r]=f[l][k-1]*f[k+1][r]+a[k]) 取得最大值时的 (k) 。特别地，若 (l=r) ,则 (p[l][l] = l)。 在进行第一个dp时就可以顺便求出来这个dp。
最后输出的时候，先找 (p[1][n]) 并输出，这个整个树的根将树分为两部分，分别递归这两部分即可。

#include <bits/stdc++.h>
using namespace std;
const int inf = 2147483647;
const int MAXN = 35;
typedef long long ll;
ll n, a[MAXN];
ll f[MAXN][MAXN];
ll p[MAXN][MAXN];
ll ans[MAXN], top;
void output(int l, int r)
{
    if (l > r)
        return;
    ll k = p[l][r];
    printf("%lld ", k);
    output(l, k - 1);
    output(k + 1, r);
}

int main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", a + i);
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            f[i][j] = 1;
    for (int i = 1; i <= n; i++)
        f[i][i] = a[i], p[i][i] = i;
    for (int len = 2; len <= n; len++)
        for (int l = 1, r = l + len - 1; r <= n; l++, r++)
            for (int k = l; k <= r; k++)
            {
                int nx = f[l][k - 1] * f[k + 1][r] + a[k];
                if (nx > f[l][r])
                {
                    f[l][r] = nx;
                    p[l][r] = k;
                }
            }

    printf("%lld
", f[1][n]);
    output(1, n);
#ifndef ONLINE_JUDGE
    system("pause");
#endif
    return 0;
}