实验讲评3实验讲评3章节.pptVIP

教学进度 计算机科学与工程系 石子合并 在一个圆形操场的四周摆放N堆石子（N≤100），现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。 ①选择一种合并石子的方案，使得做N－1次合并，得分的总和最小； ②选择一种合并石子的方案，使得做N－1次合并，得分的总和最大。 错误做法 从最上面的一堆开始，沿顺时针方向排成一个序列。 第一次选得分最小（最大）的相邻两堆合并，形成新的一堆；接下来，在N－1堆中选得分最小（最大）的相邻两堆合并……，依次类推，直至所有石子经N－1次合并后形成一堆。 例: 有5堆石子，每堆石子数（从最上面一堆数起，顺时针数）依次为7 6 5 7 100 要求选择一种合并石子的方案，使得做4次合并，得分的总和最小。 按照贪心法，合并的过程如下：? ? 每次合并得分? ? 第一次合并 7 6 5 7 100 -11? ? 第二次合并 7 11 7 ? 100-18? ? 第三次合并 18 7 ? ?100 -25? ? 第四次合并 25 100 -125 总得分＝11＋18＋25+125＝179 另一种合并方案 每次合并得分? 第一次合并 7 6 5 7 100 -13? ? 第二次合并 13 5 7 ? 100-12? ? 第三次合并 13 12 ? ?100 -25? ? 第四次合并 25 100 -125 总得分＝13＋12＋25+125＝175 使用贪心法至所以可能出错，是因为每一次选择得分最小（最大）的相邻两堆合并，不一定保证余下的合并过程能导致最优解。 做法1不可行 出错的原因——存在环？ 石子合并问题另一变形 在同一直线上依次摆放N堆石子（N≤100），现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。 如果N－1次合并的全局最优解包含了每一次合并的子问题的最优解，那么经这样的N－1次合并后的得分总和必然是最优的。 最后一次合并，肯定是2堆石子合并，如果2堆石子合并的时候的前N－2次合并是最优的，则合并完最后也是最优的。 正确做法 圆形 ?直线 n种情况1－n，2－1，3－2……n－n-1 每种情况就相当于是一个n堆石子同一直线摆放的情形 合唱队形 N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的 K位同学排成合唱队形。 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1 T2 ... Ti Ti+1 … TK (1 = i = K)。 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。 Sample Input 8 186 186 150 200 160 130 197 220 3 150 130 140 0 Sample Output 4 1 * 最长单调上升子序列 给出一个由n个数组成的序列x[1..n]，找出它的最长单调上升子序列的长度。 d[i]:以x[i]为结尾的最长单调上升子序列的长度 d[i] = max{d[j] + 1} ji x[j] x[i] 教学进度 计算机科学与工程系