P1040 [NOIP2003 提高组] 加分二叉树

#include<bits/stdc++.h>
using namespace std;
int n;
int  a[40],root[40][40];
long long dp[40][40];

long long dfs(int L,int R) {
	if(L>R) return 1;//找完
	if(dp[L][R]) return dp[L][R];//有了直接返回
	long long maxn=0;
	for(int i=L; i<=R; i++) {
		long long t=dfs(L,i-1) * dfs(i+1,R)+a[i];/*
subtree 的左子树的加分乘subtree的右子树的加分+ subtree 的根的分数。
*/
		if(t>maxn) {//记录最高分和此时的点
			maxn=t;
			root[L][R]=i;
		}
	}
	return dp[L][R]=maxn;//搜完返回并记录最大
}
void dg(int L,int R) {//前序遍历
	if(L>R) return;
	printf("%d ",root[L][R]);
	dg(L,root[L][R]-1);
	dg(root[L][R]+1,R);
}
int main() {
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
		dp[i][i]=a[i];//记录单结点数
		root[i][i]=i;//标记
	}
	printf("%lld\n",dfs(1,n));
	dg(1,n);
	return 0;
}

前序遍历：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子数。