解这道题的前提是非常熟悉中序遍历的方式

我就是因为不熟悉而没有做出来

中序遍历是5 7 1 2 10的话，如果1是根节点

那么5 7 1就是1的左子树，2， 10就是右子树

这就有点中链式dp的味道了，实际解法也是中链式dp的解法

设f[i][j]为中序遍历从i到j的最大价值

f[l][r] = f[l][mid-1] * f[mid+1][r] + d[mid]

从小规模推到大规模

dp过程中记录根节点以求前序遍历。

#include
    
     #define REP(i, a, b) for(int i = (a); i < (b); i++)using namespace std;const int MAXN = 30;int d[MAXN], f[MAXN][MAXN], root[MAXN][MAXN], n;void print(int l, int r){	if(l <= r)	{		printf("%d ", root[l][r]);		print(l, root[l][r] - 1);		print(root[l][r] + 1, r);	}}int main(){	scanf("%d", &n);	REP(i, 0, n + 1)		REP(j, 0, n + 1)			f[i][j] = 1;	REP(i, 1, n + 1) 	{		scanf("%d", &d[i]);		f[i][i] = d[i];		root[i][i] = i;	}		REP(k, 2, n + 1)		for(int l = 1; l + k - 1 <= n; l++)		{			int r = l + k - 1;			REP(mid, l, r + 1)				if(f[l][r] < f[l][mid-1] * f[mid+1][r] + d[mid])				{					f[l][r] = f[l][mid-1] * f[mid+1][r] + d[mid];					root[l][r] = mid;				}		}		printf("%d\n", f[1][n]);	print(1, n);		return 0;}