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

原题传送门

思路

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

因此我们假设一颗二叉树的根为

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})

这个式子。

代码

CPP

#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;
}

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

文章操作

原题传送门

思路

代码

相关推荐

评论

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