https://www.luogu.com.cn/problem/P1040

中序遍历，左子树+根+右子树

对于区间l到r，枚举根结点i，再分别求解区间l到i-1和i+1到r

直接搜索程序很好看但是会t

可以改为记搜或动规

原题还需要求前序遍历，如果照常对于每个点存左儿子和右儿子，在l到r的区间中的根x的儿子可能会在搜索过程中被某个奇怪的区间中的根x的值覆盖（实际上我们根本不会划出这个区间）

需要按照l到r的区间（状态划分）来存根结点

记搜

#include<bits/stdc++.h>
using namespace std;
long long a[110],m[110][110];
int ans[110][110],cnt[110],vis[110];
long long dfs(int l,int r,int father)
{
	if(m[l][r]!=-1) return m[l][r];
	if(l>r) return 1;
	if(l==r) 
	{
		ans[l][r]=l;
		return m[l][r]=a[l];
	}
	long long maxn=0,sum;
	int root;
	for(int i=l;i<=r;i++)
	{
		sum=a[i]+dfs(l,i-1,i)*dfs(i+1,r,i);
		if(sum>maxn) root=i,maxn=sum;
	}
	ans[l][r]=root;
	return m[l][r]=maxn;
}
void dfs_(int l,int r)
{
	if(l>r) return;
	cout<<ans[l][r]<<" ";
	if(l==r) return;
	dfs_(l,ans[l][r]-1);
	dfs_(ans[l][r]+1,r);
}
int main()
{
	memset(m,-1,sizeof(m));
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	cout<<dfs(1,n,0)<<"\n";
	dfs_(1,n);
	return 0;
}

动规

#include<bits/stdc++.h>
using namespace std;
long long a[110],dp[110][110];
int ans[110][110],cnt[110],vis[110];

void dfs_(int l,int r)
{
	if(l>r) return;
	cout<<ans[l][r]<<" ";
	if(l==r) return;
	dfs_(l,ans[l][r]-1);
	dfs_(ans[l][r]+1,r);
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int l=1;l<=n;l++) dp[l][l]=a[l],dp[l][l-1]=1,ans[l][l]=l;
	for(int len=1;len<=n;len++)
	for(int l=1;l<=n-len;l++)
	for(int k=l;k<=l+len;k++)
	if(dp[l][len+l]<dp[l][k-1]*dp[k+1][len+l]+a[k])
	{
		dp[l][len+l]=dp[l][k-1]*dp[k+1][len+l]+a[k];
		ans[l][len+l]=k;
	}
	cout<<dp[1][n]<<"\n";
	dfs_(1,n);
	return 0;
}