tctony

Focus on linux,emacs,c/c++,python,algorithm...

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  17 随笔 :: 0 文章 :: 7 评论 :: 0 Trackbacks
加分二叉树
【问题描述】
    设一个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
 
题意分析:(1)给出一棵树的中序遍历(1~n),以及中序遍历每个节点所对应的分值,求最高加分
        (2)n<30,结果不会超过4,000,000,000
       
算法分析:

求最高加分:
    设节点d为最优的根节点,那么可以把这棵树分成[1,d-1]和[d+1,n],这颗树的加分为子树[1,d-1]的加分与子树[d+1,n]加分的乘积与d的加分的和,而[1,d-1]和[d+1,n]的加分也可也一定是最优加分,所以这个题具有最优子结构,那么可以用动态规划

    设f[k,j]为子树k到j的最高加分,求f[k,j]的最优值,就要求f[1,d-1]和f[d+1,n]的最优加分,那么枚举根节点p,则有
    f[k,j]的最优值=f[k,p-1]*f[p+1,j]+v[p](k<p<j)
规划方程为f[k,j]=max{f[k,p-1]*f[p+1,j]+v[p]}(k<p<j)
但是,根据题目,左子树或右子树可以为空,即当k=p或p=j,于是对此特殊处理,求出这种情况下的加分,再进行比较

动态规划顺序:根据规划方程,要求f[k,j]要先求解出f[k,p-1]和f[p+1,j],即要先求出f[m,q]且q-m<j-k,那么可以根据j-k从小到大的顺序动态规划,其实就是要求一棵树的加分,先要求它的子树加分,根据树的大小作为规划顺序

打印前序遍历:
     前序遍历的顺序为根->左子树->右子树
     可以在程序中每一次更新当前子树的加分时,用sol[]记录此时的子树的根节点,那么最后纪录的就是最优的二叉树的节点
     打印时,先找出f[1,n]的根节点p,打印,然后分成f[1,p-1]和f[p+1,n]递归打印,直到打印完叶子节点


#include<iostream>
using namespace std;

#define MaxN 30
int value[MaxN];
long long treevalue[MaxN][MaxN];
int sol[MaxN][MaxN];
long long m;

void find(int i, int j){
    
if(i>j||i<0||j<0)
        
return ;
    printf(
"%d ",sol[i][j]+1);
    
if(i==j)    return ;
    find(i,sol[i][j]
-1);
    find(sol[i][j]
+1,j);
}


int main(){
    
int n,i,j,d,p;
    
while(1){
        scanf(
"%d",&n);
        
if(n==0)    
            
break;
        
        memset(treevalue,
0,sizeof(treevalue));
        memset(sol,
0,sizeof(sol));
        
for(i=0;i<n;++i){
            scanf(
"%d",&value[i]);
            treevalue[i][i]
=value[i];
            sol[i][i]
=i;
        }

        
for(i=0;i<n-1;++i){
            treevalue[i][i
+1]=value[i]+value[i+1];
            sol[i][i
+1]=i;
        }

        
        
for(d=1;d<n;++d){
            
for(i=0;i<n-d;++i){
                j
=i+d;
                
for(p=i+1;p<j;++p)
                    
if(treevalue[i][j]<(treevalue[i][p-1]*treevalue[p+1][j]+value[p])){
                        treevalue[i][j]
=treevalue[i][p-1]*treevalue[p+1][j]+value[p];
                        sol[i][j]
=p;
                    }

                    
if(treevalue[i][j]<(treevalue[i][j-1]+value[j])){
                        treevalue[i][j]
=treevalue[i][j-1]+value[j];
                        sol[i][j]
=j;
                    }

                    
if(treevalue[i][j]<(treevalue[i+1][j]+value[i])){
                        treevalue[i][j]
=treevalue[i+1][j]+value[i];
                        sol[i][j]
=i;
                    }

            }

        }

        m
=treevalue[1][n-1]+value[0];
        
if(m>treevalue[0][n-1]){
            treevalue[
0][n-1]=m;
            sol[
0][n-1]=0;
        }

        m
=treevalue[0][n-2]+value[n-1];
        
if(m>treevalue[0][n-1]){
            treevalue[
0][n-1]=m;
            sol[
0][n-1]=n-1;
        }


        printf(
"%lld\n",treevalue[0][n-1]);
        find(
0,n-1);
        printf(
"\n");
    }

    
return 0;
}
posted on 2007-12-08 15:44 tctony 阅读(1647) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理