题意

给出一个有n个节点的二叉树的中序遍历，以当前节点为根的树的分数等于左节点分数* 右节点分数+根节点分数，叶子节点的分数等于它本身，求最大分数，以及分数最大的树的先序遍历

一道区间dp题,因为要求为中序遍历，便可dp转移，枚举i,j中的树根k,转移最大值

概念:

先序遍历：根左右

中序遍历；左根右

后序遍历：左右根

状态:f[i][j]从编号由i到j的所以树中最大得分

转移方程 f[i][j]= f[i][k-1] * f[k+1][j] + f[k][k] (k>=i&&k<=j) 保证i<j

第二个问题可以再开个数组root[i][j]表示f[i][j]选择最大子树的根,然后先序遍历输出即可

代码

#include<cstdio>

using namespace std;

int n,v[40],f[40][40],root[40][40];

void dfs(int l,int r){

	if(l>r) return;

	printf("%d ",root[l][r]);

	if(l==r) return;

	dfs(l,root[l][r]-1);

	dfs(root[l][r]+1,r);

}

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;++i) scanf("%d",&f[i][i]),f[i][i-1]=1,root[i][i]=i;

	for(int i=n;i>=1;i--){

		for(int j=i+1;j<=n;++j){

			for(int k=i;k<=j;++k){

				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;

                }

			}

		}

	}

	printf("%d\n",f[1][n]);

	dfs(1,n);

	return 0;

}