pku 2486 apple tree
解法:
/////////////////////////////////////////////////////////////////////
//Apple Tree
//数组二维go,bk
//go[t][i]代表节点t的所有子树上走i步不返回,取得的最大苹果数
//bk[t][i]代表节点t的所有子树上走i步并返回,取得的最大苹果数
//求节点为x,实行不断合并子树求最优值
//当前合并到了q棵子树:
//go[x][i]就是这q棵子树上走i步不返回的最优值
//bk[x][i]就是这q棵子树上走i步并返回的最优值
//合并第q+1棵子树(不妨设第q+1棵子树的根为y)的时候,有
//go[x][i] = max( bk[x][j]+go[y][i-j], bk[y][j]+go[x][i-j] ), j=0.....i
//bk[x][i] = max( bk[x][j]+bk[y][i-j] ) j=0,.....i;
////////////////////////////////////////////////////////////////////////////
代码:
http://www.cppblog.com/qywyh/articles/18618.html
posted on 2007-02-10 18:58
豪 阅读(883)
评论(2) 编辑 收藏 引用 所属分类:
算法&ACM