原题链接
挺水的一道区间(DP)。
设(f[i][j])表示在中序遍历下编号(i sim j)的点所构成的子树的最高加分，枚举(k)为子树的根，则有状态转移方程：
[f[i][j] = max limits _{k = i + 1} ^ {j - 1} { f[i][k - 1] imes f[k + 1][j] + f[k][k] }
]
初始化(f[i][i])为点(i)的分数，(f[i][j] = f[i][i] + f[i + 1][j])，即左子树为空。
因为题目并没有说清楚，实际上要求的前序遍历是所有解中字典序最小的，所以我们要尽量使得编号小的作为根或是左子树中的点，按编号从小到大枚举哪个作为根即可。
求前序遍历可以定义(r[i][j])表示在中序遍历下编号(i sim j)的点所构成的子树的最高加分所选择的根，在(DP)过程中不断更新，最后递归输出即可。
#include<cstdio>
using namespace std;
typedef long long ll;
const int N = 50;
ll f[N][N];
int r[N][N];
inline int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c < '0' || c > '9'; c = getchar())
p |= c == '-';
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return p ? -x : x;
}
void pr(int x, int y)
{
if (x > y)
return;
printf("%d ", r[x][y]);
pr(x, r[x][y] - 1);
pr(r[x][y] + 1, y);
}
int main()
{
int i, j, k, l, n;
n = re();
for (i = 1; i <= n; i++)
f[i][i] = re(), r[i][i] = i;
for (l = 2; l <= n; l++)
for (i = 1; i + l - 1 <= n; i++)
{
j = i + l - 1;
f[i][j] = f[i][i] + f[i + 1][j];
r[i][j] = i;
for (k = i + 1; 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];
r[i][j] = k;
}
}
printf("%lld
", f[1][n]);
pr(1, n);
return 0;
}