题目链接：https://www.luogu.com.cn/problem/P1040

大意是给出一个树的中序遍历，这个树每个子树都有一个加分，得分 = 左子树分数*右子树分数+根的分数。
在每个节点都有一个分数，第i个节点分数为di。其实就是给出的中序。求最大加分并输出先序遍历

根据题意的中序，我们可以将这个数划分为左右子树。f[i][i]就是这个根的分数。我们定义f[i][j]就是i到j这个子树的最大加分，中间用k来做一个区间dp
然后对树进行一个左右子树划分求出每个子树的最优值，最后的根权值肯定是最大加分
在每个最优的情况下，我们可以记录他的根。输出先序遍历就根据这个root数组来看。

code：

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
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;
}
const int nn = 50;
int f[nn][nn],root[nn][nn];
int a[nn];
void print_path(int l,int r){
	if(l>r) return;
	if(l==r){
		cout<<l<<' ';
		return; 
	}
	cout<<root[l][r]<<' ';
	print_path(l,root[l][r]-1);
	print_path(root[l][r]+1,r);
}
int main()
{
 	//cin.ignore(numeric_limits<streamsize>::max(),'\n')
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n;
	cin>>n;
	int x;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		f[i][i]=a[i];f[i][i-1]=1;
	}
	for(int i=n;i>=1;i--){//左边的一定是左子树的根 
		for(int j=i+1;j<=n;j++){
			for(int k=i;k<=j;k++)//区间dp用于分割左右子树
			{
				if(f[i][j]<f[i][k-1]*f[k+1][j]+f[k][k]){
					f[i][j] = f[i][k-1]*f[k+1][j]+f[k][k];
					root[i][j] = k;
				}	
			}
		}
	}
	cout<<f[1][n]<<endl;
	print_path(1,n);
}

同样的，我们可以对这个树进行搜索，先进行左子树，然后进行右子树，遍历到叶子就是1. 很容易可以想到是一个递归的思想。

code：

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
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 n,m;
const int nn = 40;
int f[nn][nn];
int root[nn][nn];
int a[nn];
int dfs(int l,int r){
	if(l>r) return 1;
	if(f[l][r]) return f[l][r];
	for(int i=l;i<=r;i++){
		ll t = dfs(l,i-1)*dfs(i+1,r)+a[i];
		if(f[l][r]<t){
			f[l][r] = t;
			root[l][r] = i;
		}
	}
	return f[l][r];
}
void print_path(int l,int r){
	if(l>r) return;
	cout<<root[l][r]<<' ';
	print_path(l,root[l][r]-1);
	print_path(root[l][r]+1,r);
}
int main()
{
 	//cin.ignore(numeric_limits<streamsize>::max(),'\n')
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		root[i][i] = i;
		f[i][i] = a[i];
	}
	cout<<dfs(1,n)<<endl;
	print_path(1,n);
}