陈瑜希多角度思考创造性思维.pptVIP

优秀精品课件文档资料 多角度思考 创造性思维 ----运用树型动态规划解题的思路和方法探析 江苏省南京外国语学校 陈瑜希 引入 信息学竞赛中通常会出现这样的问题：给一棵树，要求以最少的代价（或取得最大收益）完成给定的操作 有很多问题都是在树和最优性的基础上进行了扩充和加强，从而变成了棘手的问题 这类问题通常规模较大，枚举算法的效率无法胜任，贪心算法不能得到最优解，因此要用动态规划解决 引入 在近几年信息学竞赛中，需要运用树型动态规划解决的问题频繁出现 这些问题变化繁多，各类思想精华渗透其中，对选手分析问题的能力和解题创造性思维有着较高的要求，因此它在竞赛中占据了重要地位 引入 在此，我将分析近几年国际比赛、全国比赛中的树型动态规划问题，重点探讨几种树型动态规划问题的解法，并从这些问题的分析过程中，提炼出解决这类问题的思想方法——多角度思考，创造性思维。 旨在论述解决问题的思维过程，而不仅仅是解题方法 例题解析 NOI03 逃学的小孩 IOI05 河流 NOI06 网络收费 POI04 山洞 问题描述 n个伐木的村庄 在0号结点有一个巨大的伐木场，木料被砍下后，顺着河流而被运到0号结点的伐木场 为了减少运输木料的费用，再额外建造k个伐木场 这些伐木场建造后，木料可以在运输过程中第一个碰到的新伐木场被处理。 问题描述 所有的河流都不会分叉，也就是说，每一个村子，顺流而下都只有一条路到0号结点。 已知每个村子每年要产多少木料，求在哪些村子建设伐木场能获得最小的运费。 N≤100 K≤50 问题抽象 本题的题意很明确，即建立k个伐木厂，使得把所有木材运送到最近的祖先伐木厂的费用最小。 由于题目给定的是一棵树，数据规模又比较大，很容易联想到树型动态规划。 状态的确立 首先必须有的是当前点及以当前点为根的子树中，一共建立了多少伐木厂，但是这显然是不够的，因为这个状态中没有任何与伐木厂位置相关的信息。因此我们还需要再加一维。加上有关伐木厂的位置的信息。 表示把以from为根的子树中建立kleft个伐木厂，把木材全部运送到最近的祖先伐木厂，所需要的费用，并且from有一个祖先伐木厂为to_。 （注意到这里to_仅仅是from的祖先伐木厂，而未必是from的最近祖先伐木厂，这是为什么呢？） 状态的转移 状态转移分2种情况讨论： 在from建立伐木厂 不在from建立伐木厂 状态的转移 在from建立伐木厂： 即分配kleft个伐木厂给from的子结点，使得费用最小。这分配的过程，也就相当于背包问题。 h1是用来解背包问题的临时数组，son是from的儿子结点。 状态的转移 不在from建立伐木厂： 依然是分配kleft个伐木厂给from的子结点，使得费用最小。 不过不同的是，权不是 而是 ，因为from处不一定有伐木厂。 h2是用来解背包问题的临时数组，son是from的儿子结点。 状态的转移 最后 效率分析 由于状态是3维的，而转移时需要枚举k、son、和j，看上去时间复杂度巨大。 这是为什么? 刚才的分析通过状态量和转移量相乘来分析效率，每一维都不到N。 j的总数是n，son的总数也是n，所以虽然要枚举3个，但是总的运算量是一定的，时间复杂度为 　 。 回顾 本题的动态规划是多维的，要通过分析建立状态 在兄弟结点之间要通过类似背包问题的思想进行第二次动态规划 不是单纯的根据状态量和转移量分析时间复杂度，而是根据转移总量分析 总量分析 均摊分析 例题解析 NOI03 逃学的小孩 IOI05 河流 NOI06 网络收费 POI04 山洞 问题描述 M=2N个点，构成一个满二叉树 配对收费：对于每两个用户i, j (1≤i j ≤2N ) 进行收费。 用户可以自行选择两种付费方式A、B中的一种，收取的费用等于每两位不同用户配对产生费用之和。 问题描述 I付费方式 J付费方式 nA与nB大小关系 付费系数k 实际付费 A A nAnB 2 k * Fi, j A B 1 B A 1 B B 0 A A nA≥nB 0 A B 1 B A 1 B B 2 问题描述 对于用户i，如果他/她想改变付费方式（由A改为B或由B改为A），就必须支付Ci元给网络公司以修改档案。 给定每个用户注册时所选择的付费方式以及Ci，试求这些用户应该如何选择自己的付费方式以使得总费用最少（更改付费方式费用+配对收费的费用）。 N≤10 问题转化 配对收费的规则 B较多时， AA 收费系数为2 AB 收费系数为1 BB 收费系数为0 其他情况反之 设想： B较多时