题解：P1040 [NOIP 2003 提高组] 加分二叉树

Fire__Fly · 2025-03-27 21:04:50 · 题解

原题传送门

思路

首先二叉树的中序遍历具有左孩子遍历序列一定在根结点的左边，右孩子遍历序列一定在根结点的右边的性质。

因此我们假设一颗二叉树的根为 k，中序遍历为 (1,2,3,\ldots,n) 则它的左儿子为 (1,2,3,\ldots,k-1) 右儿子为 (k+1,k+2,k+3,\ldots,n)。

所以我们令 dp_{i,j} 表示中序遍历为 (i,i+1,i+2,\ldots,j) 的二叉树的最大加分，那么我们很容易就可以推出 dp_{i,j}=\max(dp_{i,k-1} \times dp_{k+1,j}+d_{k}) 这个式子。

代码

#include<bits/stdc++.h>
#define int long long
#define inf 0x7f7f7f7f
using namespace std;
const int maxn = 1e6 + 100;
inline int read() {
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int dp[50][50] , n , val[50] , root[50][50];
inline int dfs(int l , int r) {
    if(l == r) {
        root[l][r] = r;
        dp[l][r] = val[l];
        return dp[l][r];
    }
    if(l > r) {
        root[l][r] = 0;
        dp[l][r] = 1;
        return dp[l][r];
    }
    if(dp[l][r]) return dp[l][r];
    for(int i = l; i <= r; i++) {
        int tl = dfs(l , i - 1) , tr = dfs(i + 1 , r);
        if(tl * tr + val[i] > dp[l][r]) dp[l][r] = tl * tr + val[i] , root[l][r] = i;
    }
    return dp[l][r];
}
inline void bl(int l , int r) {
    if(!root[l][r]) return ;
    cout << root[l][r] << " ";
    bl(l , root[l][r] - 1);
    bl(root[l][r] + 1 , r);
}
signed main() {
    n = read();
    for(int i = 1; i <= n; i++) val[i] = read();
    cout << dfs(1 , n) << endl;
    bl(1 , n);
    return 0;
}