【问题描述】
设 一个 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 个用空格隔开的整数，为该树的前序遍历。
【输入样例】
5
5 7 1 2 10
【输出样例】
145
3 1 2 4 5题解： 本题是树形DP，是本人第一个接触的树形DP，（略激动！！），其实并没有想象中的那么难，呵呵，因为题目中给的是中序遍历，所以，从左到右每一个数都有可能是根节点，而不像先序或者后序那样只能是第一个或者第二个是根节点，由此可以写出状态转移方程：q[i][j]=max(q[i][j],q[i][k-1]*q[k+1][j]+q[k][k]);i和j表示从点i到点j的最大加分，k是枚举的根节点，也就是，i到j中，每一个都有可能是根节点，所以要枚举取最大的那一个，呵呵，还有初始化一定要全部初始为1，要不会出事，本题还有一点要小动点脑筋，就是记录当q[i][j]取最大值时的根节点，这样才能最后输出先序遍历，呵呵，我用的时root[i][j],表示q[i][j]的根节点，最后输出时一个递归就行了，呵呵！上程序吧！ 感谢星光大牛指点！！ 原程： C++语言: made by PaulInsider!
#include<iostream> #include<cstdio> #include<cstdlib> #define max(a,b) ((a)>=(b)?(a):(b))
using namespace std;
int n,q[31][31],root[31][31];
void di(int x,int y);
int main()
{
freopen ("jfecs.in","r",stdin);
freopen ("jfecs.out","w",stdout);
scanf("%d",&n);
for (int e=0;e<=n;e++)
{
for (int r=0;r<=n;r++)
{
q[e][r]=1;
}
}
for (int o=1;o<=n;o++)
{
scanf("%d",&q[o][o]);
root[o][o]=o;
}
int j;
for (int l=1;l<=n-1;l++)
{
for (int i=1;i<=n;i++)
{
j=i+l;
if (j<=n)
{
for (int k=i;k<=j;k++)
{
if (q[i][j]<q[i][k-1]*q[k+1][j]+q[k][k])
{
q[i][j]=max(q[i][j],q[i][k-1]*q[k+1][j]+q[k][k]);
root[i][j]=k;
}
}
}
}
}
cout<<q[1][n]<<endl;
cout<<root[1][n];
di(1,root[1][n]-1);
di(root[1][n]+1,n);
return 0;
}
void di(int x,int y)
{
if (x<=y)
{
cout<<' '<<root[x][y];
di(x,root[x][y]-1);
di(root[x][y]+1,y);
}
}
|