题目链接：https://www.luogu.org/problemnew/show/P1040
题意：
某一个二叉树的中序遍历是1~n，每个节点有一个分数（正整数）。
二叉树的分数是左子树分数乘右子树分数加根节点分数，如果子树为空分数是1.
现在想知道这个二叉树最大的分数是多少，并且输出前序遍历结果。
思路：
$f[i][j]$表示$i$~$j$号节点组成的子树的最大分数，为了最后能输出前序遍历结果用$root[i][j]$表示$i~j$号节点组成的子树的根
枚举根节点，记忆化搜索。
//#include<bits/stdc++>
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdlib.h>
#include<queue>
#include<map>
#include<stack>
#include<set> #define LL long long
#define ull unsigned long long
#define inf 0x3f3f3f3f using namespace std;
int n;
int sco[];
LL f[][];
int root[][];
bool flag = false; LL dfs(int i, int j)
{
if(f[i][j]) return f[i][j];
if(j < i){
//root[i][j] = i;
return ;
} for(int k = i; k <= j; k++){
LL t = dfs(i, k - ) * dfs(k + , j) + sco[k];
if(f[i][j] < t){
root[i][j] = k;
f[i][j] = t;
}
}
return f[i][j];
} void print(int i, int j){
if(i > j){
return;
}
if(flag)printf(" ");
else{
flag = true;
}
printf("%d", root[i][j]);
print(i, root[i][j] - );
//printf(" %d", root[i][j]);
print(root[i][j] + , j);
return;
} int main()
{
scanf("%d", &n);
for(int i = ; i <= n; i++){
scanf("%d", &sco[i]);
f[i][i] = sco[i];
root[i][i] = i;
}
LL ans = dfs(, n);
cout<<ans<<endl;
print(, n);
return ;
}