解这道题的前提是非常熟悉中序遍历的方式
我就是因为不熟悉而没有做出来
中序遍历是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<cstdio>
#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;
}