新手启示者
设一个n个节点的二叉树tree的中序遍历为（1,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），即第j个节点的分数为dj，tree及它的每个子树都有一个加分，任意棵子树subtree（也包含tree本身）的加分计算方法如下：
subtree的左子树的加分*subtree的右子树的加分+subtree的根的分数
若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数，不考虑它的空子树。
试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出：
1）tree的最高加分
2）tree的前序遍历
输入描述 Input Description
第1行：一个整数n（n<30），为节点个数。
第2行：n个用空格隔开的整数，为每个节点的分数（分数<100）。
输出描述 Output Description
第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。
第2行：n个用空格隔开的整数，为该树的前序遍历。
样例输入 Sample Input
5 5 7 1 2 10
样例输出 Sample Output
145 3 1 2 4 5
数据范围及提示 Data Size & Hint
n<=30
分数<=100
资深光能
树形DP啊！！！！
修练者
我没权限查看，我很抱歉。
新手启示者
@
@@
@@@
@@@@
@@@@@
@@@@@@
@@@@@@@
@@@@@@@@
@@@@@@@@@
@@@@@@@@@@
@@@@@@@@@@@
@@@@@@@@@@@@
@@@@@@@@@@@@@
@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@
新手守护
我也没权限查看我很抱歉
资深守护
你学到这了吗？？
（ps:不会）
新手启示者
DIDA
新手启示者
DIDA
初级光能
主函数：
for (int i=0; i<maxn; ++i)
for (int j=0; j<maxn; ++j)
f[i][j]=1;
scanf("%d", &n);
for (int i=1; i<=n; ++i)
scanf("%d", &score[i]);
dfs(1, n);
printf("%d\n", f[1][n]);
print(1, n);
主函数外：
const int maxn=35;
int n, score[maxn];
int f[maxn][maxn], root[maxn][maxn];
void dfs(int l, int r){
if (l>r) return;
if (f[l][r]!=1) return;
if (l==r){ f[l][r]=score[l]; return; }
int tmp;
for (int i=l; i<=r; ++i){
dfs(l, i-1);
dfs(i+1, r);
tmp=f[l][i-1]*f[i+1][r]+score[i];
if (tmp>f[l][r]){ f[l][r]=tmp; root[l][r]=i; }
}
}
void print(int l, int r){
if (l>r) return;
if (l==r) printf("%d ", l);
else {
printf("%d ", root[l][r]);
print(l, root[l][r]-1);
print(root[l][r]+1, r);
}
}
盛慧慧在2021-05-19 20:18:53追加了内容
采纳谭迪元！！！
盛慧慧在2021-05-19 20:19:11追加了内容
他告诉我的
