加分二叉树

加分二叉树

时间: 1ms        内存:128M

描述:

设一个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

提示:

参考答案(内存最优[760]):

#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("%d\n", f[1][n]);
     print(1, n);
     for (i = 1; i < t; i++) 
		 printf("%d ", ans[i]);
     printf("%d\n", 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,然后递归寻找方案并记录.*/

参考答案(时间最优[0]):

#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("%d\n", f[1][n]);
     print(1, n);
     for (i = 1; i < t; i++) 
		 printf("%d ", ans[i]);
     printf("%d\n", 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,然后递归寻找方案并记录.*/

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注