题目中说二叉树的中序遍历是顺序的，这说明：对于区间[i,j]其根root满足i<=root<=j
也就是说，对于区间[i,j]其最大加分为选取其中一个作为根R，其左边[i,R-1]的最大加分乘以[R+1,j]区间最大加分+Value[R]，对于所有可能的R取表达式最大值.状态转移方程：
\(f[i][j] = Max\left\{ {f[i,k – 1] \times f[k + 1][j] + v[k] ~|~ k = i~to~j} \right\}\)注意：题目要求若一棵树没有左或者右子树，则其加分为存在的那棵子树
初始值for i=1 to n f[i][i]=v[i];
输出便利的方法是：每次记录取到最大值时的根节点编号，设Node[i][j]=x表示在[i][j]区间取到最大加分的数的根节点为x
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <stdio.h> int n; int v[40]; __int64 arr[40][40];//表示从i到j的最大加分 int nod[40][40];//表示[i,j]区间根 __int64 gm(int b,int e){//Get Max int i;__int64 x; if (arr[b][e]>0 ) return arr[b][e];//记忆化搜索 //缺少左或右子树的情况 if (e-b<2) {nod[b][e]=b;arr[b][e]=v[b]+v[e];return arr[b][e];} for (i=b+1;i<e;i++){ x=gm(b,i-1)*gm(i+1,e)+v[i]; if (x>arr[b][e]){ arr[b][e]=x; nod[b][e]=i; } } return arr[b][e]; } void print(int b,int e){//输出先序遍历 if (b==e ){printf("%d ",b);return;} printf("%d ",nod[b][e]); if (nod[b][e]!=b)print(b,nod[b][e]-1); if (nod[b][e]!=e)print(nod[b][e]+1,e); } int main(){ int i,j; scanf("%d",&n); for (i=1;i<=n;i++) for (j=1;j<=n;j++) arr[i][j]=-1; for (i=1;i<=n;i++){ scanf("%d",&v[i]); arr[i][i]=v[i]; nod[i][i]=i; } printf("%I64d\n",gm(1,n)); //for (i=1;i<=n;i++){ for (j=1;j<=n;j++)printf("%3d",nod[i][j]);printf("\n");} print(1,n); //getch(); return 0; } /* 中序遍历有序说明在[i,j]区间内的最大加分可由选择的中间点表示状态 */ |
题目描述
设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：
subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数
若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空
子树。
试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出；
（1）tree的最高加分
（2）tree的前序遍历
输入格式
第1行：一个整数n（n＜30），为节点个数。
第2行：n个用空格隔开的整数，为每个节点的分数（分数＜100）。
输出格式
第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。
第2行：n个用空格隔开的整数，为该树的前序遍历。
样例输入
样例输出
原创文章，转载请注明： 转载自Comzyh的博客
本文链接地址: P49 加分二叉树 题解