题目描述
设一个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
参考代码
#include<stdio.h>
#include<stdlib.h>
int f[35][35] = {0}, d[35][35] = {0}, ans[35] = {0}, t = 0;
void print(int start, int end)
{
if (start > end)
return;
if (start == end)
{
ans[++t] = start;
return;
}
ans[++t] = d[start][end];
print(start, d[start][end]-1);
print(d[start][end]+1, end);
}
int main()
{
int n, a[35] = {0}, i, j, k, l;
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
f[i][i-1] = 1;
f[i][i] = a[i];
}
for (l = 2; l <= n; l++)
for (i = 1; i <= n; i++)
for (k = i; k <= i+l-1; k++)
{
j = i+l-1;
if (f[i][j] < f[i][k-1]*f[k+1][j] + a[k])
{
f[i][j] = f[i][k-1]*f[k+1][j] + a[k];
d[i][j] = k;
}
}
printf("%dn", f[1][n]);
print(1, n);
for (i = 1; i < t; i++)
printf("%d ", ans[i]);
printf("%dn", ans[t]);
return 0;
}
/*
é¢ç®ä¸æè¿ä¹ä¸å¥è¯âè¥æ个åæ 为主ï¼è§å®å
¶å å为1âï¼
è¿å¥è¯åºè¯¥æ¯âè¥æ个åæ 为空ï¼è§å®å
¶å å为1âã
æ å½¢DPï¼éè¦è®°å½æ¹æ¡ï¼å¹¶æ³¨æ空æ çæ
åµ.
[ç¶æ]f[i][j]ä»ç»ç¹iå°jçæ大å åå¼
[æ¹ç¨]f[i][j] = max{f[i][k-1]*f[k+1][j]+a[k]} (i<=k<=j)
å®ç°æ¹ç¨çæ¶å循ç¯é¡ºåºé常å
³é®:ç»ç¹æ°ç±å°å°å¤§å¾ªç¯.å¦åä¼åºç°éè¦çå¼æªè®¡ç®çæ
åµ.
è®°å½æ¹æ¡å¯ä»¥ç¨ä¸ä¸ªæ°ç»d[i][j]è®°å½kï¼ç¶åéå½å¯»æ¾æ¹æ¡å¹¶è®°å½.*/
解析
暂无