单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级树型动态规划JSOI2010冬令营引言树是一种特殊的图可以描述比较复杂的关系而大多数动归都是在一维二维这种规则的背景下的再加上树递归定义的性质可以说是一种非常合适的动归框架树型动态规划就成为动规中重要的一类题型因为树可以描述比较复杂的关系这对选手分析问题的能力有较高的要求在寻找最优子结构组织状态时往往需要创造性思维而且树型动态

单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级LETS USE LINUX树型动态规划长沙市雅礼中学 朱全民加分二叉树给定一个中序遍历为123…n的二叉树每个结点有一个权值定义二叉树的加分规则为：左子树的加分× 右子树的加分根的分数若某个树缺少左子树或右子树规定缺少的子树加分为1构造符合条件的二叉树该树加分最大输出其前序遍历序列样例中序遍历为12345的二叉树有很多下图