上善若水

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  2 Posts :: 32 Stories :: 2 Comments :: 0 Trackbacks

常用链接

留言簿

我参与的团队

最新随笔

搜索

  •  

积分与排名

  • 积分 - 10150
  • 排名 - 1170

最新评论

阅读排行榜

评论排行榜

加分二叉树

时间限制(普通/Java):1000MS/10000MS          运行内存限制:65536KByte
总提交:191            测试通过:67

描述

 设一个n个节点的二叉树tree的中序遍历为(l,2,3,…,n),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整数),记第j个节点的分数为ditree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree本身)的加分计算方法如下:

    subtree的左子树的加分× subtree的右子树的加分+subtree的根的分数

    若某个子树为主,规定其加分为1,叶子的加分就是叶节点本身的分数。不考虑它的空

子树。

    试求一棵符合中序遍历为(1,2,3,…,n)且加分最高的二叉树tree。要求输出;

    1tree的最高加分

    2tree的前序遍历

 

输入

    1行:一个整数nn30),为节点个数。

    2行:n个用空格隔开的整数,为每个节点的分数(分数<100)。

 

输出

    1行:一个整数,为最高加分(结果不会超过4,000,000,000)。

    2行:n个用空格隔开的整数,为该树的前序遍历。

 

样例输入

5
5 7 1 2 10

样例输出

145
3 1 2 4 5

题目来源

NOIP2003



[分析]很显然,本题适合用动态规划来解。如果用数组value[i,j]表示从节点i到节点j所组成的二叉树最大加分,则动态方程可以表示如下:
value[i,j]=max{value[i,i]+value[i+1,j],value[i+1,i+1]+value[i,i]*value[i+2,j], value[i+2,i+2]+value[i,i+1]*value[i+3,j],…,value[j-1,j-1]+value[i,j-2]*value[j,j], value[j,j]+value[i,j-1]}
题目还要求输出最大加分树的前序遍历序列,因此必须在计算过程中记下从节点i到节点j所组成的最大加分二叉树的根节点,用数组root[i,j]表示
//动态规划+前序遍历节点
#include <stdio.h>
#include 
<string.h>
int flag=0,root[31][31],n;
void out(int a,int b);
int main()
{
    
int i,j,k,head,_max,dp[31][31];
    scanf(
"%d",&n);
    
for (i=0;i<n+2;i++)
    
{
        
for (j=0;j<n+2;j++)
        
{
            dp[i][j]
=1;
        }

    }


    
for (i=1;i<=n;i++)
    
{
        scanf(
"%d",&dp[i][i]);
    }

    
for (i=1;i<n;i++)//i为间隔
    {
        
for (j=1;j<n-i+1;j++)
        
{
            _max
=0;
            
for (k=j;k<=i+j;k++)//找根节点k  左子树i
            {
                
if(_max<dp[j][k-1]*dp[k+1][j+i]+dp[k][k])
                
{
                    _max
=dp[j][k-1]*dp[k+1][j+i]+dp[k][k];
                    root[j][j
+i]=k;
                }

            }

            dp[j][j
+i]=_max;
        }

    }

    printf(
"%d\n",dp[1][n]);
    
out(1,n);
}

void out(int a,int b)

    
if(a>b) return
    
if(a==b)
        flag
++;
        
if (flag==n)
        
{
         printf(
"%d\n",a);
        }

        
else printf("%d ",a); 
        
return;        
    }
 
    flag
++;
    
if (flag==n)
    
{
     printf(
"%d\n",root[a][b]);
    }

    
else 
        printf(
"%d ",root[a][b]);
    
out(a,root[a][b]-1); 
    
out(root[a][b]+1,b); 
}

posted on 2009-11-21 23:19 上善若水 阅读(468) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理