题意概括
————————————————————
有一个n个节点二叉树，每个节点都有一个价值a[i]，且这棵树的中序遍历为 1~n
这个树中的任意一个子树（包含这棵树本身）的价值有以下的定义：
子树的价值 = 根节点的价值 + 左子树的价值 * 右子树的价值
问这棵树的最大价值为多少？并且要求求出这棵树的先序遍历
题目思路
————————————————————
问这棵树的最大价值？
这个问题其实可以进行分解：
一棵树的最大价值 = 左子树的最大价值*右子树的最大价值 + 根节点的价值
同理：这棵树的左子树的最大价值也可以分解成类似的问题
这样一来我们可以把问题规模不断地缩小……
那么，缩小到什么程度呢？
那废话，肯定是分无可分的时候啦~~~~~~
代码实现
——————————————————————
#include<bits/stdc++.h>
#define int long long
using namespace std;
const long long maxn=35;
int n;
int a[maxn];
int dp[maxn][maxn],t[maxn][maxn],cnt; // dp用来记录l~r的最大值，t用来记录l~r的根节点
void dfs(int l,int r) //追溯 l~r 的根节点
{
if(l > r)return ;
cout<<t[l][r]<<" ";
dfs(l,t[l][r]-1);
dfs(t[l][r]+1,r);
}
int DFS(int l,int r)
{
if(l > r) return 1;//此时已经分无可分了，那最大值就是1
if(l == r) {
t[l][r] = l;//相等的时候根节点就是本身
return a[l]; //相等时最大值也是本身
}
if(dp[l][r] != -1)return dp[l][r]; //记忆化搜索
int ans=INT_MIN,id;
for(int i=l;i<=r;i++){ // 枚举根节点 将树分为 l~i-1 （左子树）， i（根节点） ，i+1 ~ r（右子树）
int tmp=DFS(l,i-1)*DFS(i+1,r)+a[i];
if(ans < tmp){
ans=tmp;
id = i;
}
}
t[l][r] = id;//记录根节点
return dp[l][r] = ans;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
for(int j=1;j<=n;j++){
dp[i][j] = -1; //初始化
}
}
cout<<DFS(1,n)<<endl; //输出问题最大值
dfs(1,n); //输出前序遍历
return 0;
}