当前位置:首页 >> 数学 >>

动态规划习题精讲


信息学竞赛中的动态规划专题
哈尔滨工业大学 周谷越 【关键字】 动态规划 动机 状态 典型题目 辅助方法 优化方法 【摘要】 本文针对信息学竞赛 (面向中学生的 Noi 以及面向大学生的 ACM/ICPC) 中的动态规划 算法,从动机入手,讨论了动态规划的基本思想和常见应用方法。通过一些常见的经典题目 来归纳动态规划的一般作法并从理论上加以分析和说明。 并介绍了一些解决动态规划问题时 的一些辅助技巧和优化方法。 纵观全文可知, 动态规划的关键在于把握本质思想的基础上灵 活运用。 【目录】 1.动态规划的动机和基本思想 1.1.解决重复子问题 1.2.解决复杂贪心问题 2.动态规划状态的划分方法 2.1.一维状态划分 2.2.二维状态划分 2.3.树型状态划分 3.动态规划的辅助与优化方法 3.1.常见辅助方法 3.2.常见优化方法 4.近年来 Noi 动态规划题目分析 4.1 Noi2005 瑰丽华尔兹 4.2 Noi2005 聪聪与可可 4.3 Noi2006 网络收费 4.4 Noi2006 千年虫 附录 参考书籍与相关材料

信息学竞赛中的动态规划专题

1.动态规划的动机和基本思想
首先声明,这里所说的动态规划的动机是从竞赛角度出发的动机。 1.1 解决重复子问题 对于很多问题,我们利用分治的思想,可以把大问题分解成若干小问题,然后再把各个 小问题的答案组合起来, 得到大问题的解答。 这类问题的共同点是小问题和大问题的本质相 同。很多分治法可以解决的问题(如 quick_sort,hanoi_tower 等)都是把大问题化成 2 个以 内的不相重复的小问题,解决的问题数量即为∑(log2n / k)。而考虑下面这个问题: USACO 1.4.3 Number Triangles http://122.139.62.222/problem.php?id=1417 【题目描述】 考虑在下面被显示的数字金字塔。 写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大。 每一步 可以走到左下方的点也可以到达右下方的点。 7 38 810 2744 45261 在上面的样例中,从 7 到 3 到 8 到 7 到 5 的路径产生了最大和:30。 【输入格式】 第一个行包含 R(1<= R<=1000) ,表示行的数目。 后面每行为这个数字金字塔特定行包含 的整数。所有的被供应的整数是非负的且不大于 100。 【输出格式】 单独的一行包含那个可能得到的最大的和。 【样例输入】 5 7 38 810 2744 45261 【样例输出】 30 显然, 我们同样可以把大问题化成小问题来解决。 如样例中最底层的 6 就可以从次底层
第 1 页/共 50 页

信息学竞赛中的动态规划专题

的两个 4 走来, 假设分别知道走到次底层的两个 4 的最优解, 那么取其中较大的加上 6 就是 走到最底层的 6 时的最优解。然而次底层的两个 4 还可以走向最底层的 2 和 1,这样就产生 了重复的子问题。动态规划的第一类动机就是为了要避免这种重复运算。 事实上,子问题的个数是确定的,只要我们能够把已经计算过的子问题记录下来,再下 次需要时直接使用,便可以大大提高程序的效率。 下面介绍一下动态规划的相关概念。 首先动态规划是来解决最优化问题的, 再进一步说 就是解决最优化问题中的多阶段决策问题。 以下是动态的定义内容,在各种基础书籍上都有相关讲解,在此仅列出,不做累述。 状态(State) :表示事物的性质,是描述动态规划中的单元的量。 阶段(Stage) :阶段是一些性质相近的状态集合。 决策(Decision) :每个阶段做出的某种选择性行动,是程序所需要完成的选择。 状态转移方程(Equal) :是前一个阶段的状态转移到后一个的状态的演变规律,是关于 两个相邻阶段状态变化的方程,是动态规划的核心。 初始状态:由已知能够确定的状态。 目标状态:表示解或能够转化为解的状态。 总体看来,由初始状态经过若干阶段通过若干决策推出目标状态的过程就是动态规划。 下面我们就 Number Triangles 一题对这些概念对号入座: 首先确定状态,用 F[I,J]表示从顶层走到第 I 行第 J 列的点能取得的最大和。显然每一 层为一个阶段。 而对于走到每一个非顶层点的情况来说, 最多都只可能由它上方的点或左上 方的点走来。 则有状态转移方程: F[I,J] = Max (F[I-1,J], F[I-1,J-1]) + A[I,J]; 初始状态为 F[1,1] = A[1,1];目标状态为 F[N,K],其中 K∈[1,N]。要求输出的解则是 Max {F[N,K]} ,其中 K ∈[1,N]。时空复杂度均为 O(N2) 。 这里给出程序主干部分: F[1,1] = A[1,1] For I = 2 to N Do For J = 1 to I Do If F[I-1,J] > F[I-1,J-1] Then F[I,J] = F[I-1,J] + A[I,J] Else F[I,J] = F[I-1,J-1] + A[I,J] 接下来我们从理论上来讨论使用动态规划的条件。 对于一种状态划分的方法来说, 状态 只与状态本身的性质有关,而与如何达到该状态等其他条件一概无关的性质叫做无后效性。 由于存在无后效性, 决策只能从决策本身的性质来确定, 使得某一阶段的状态只与它所在阶 段的前一阶段的状态有关。可以看出,存在无后效性是应用动态规划的前提条件。而考虑动 态规划的正确性时,问题则需要满足最优子结构。所谓最优子结构,即当前一阶段的状态最 优时,通过状态转移方程得到的状态也能达到最优。理论上看,无后效性和最优子结构是 使用动态规划时的两个基本条件,而具体应用动态规划时更多凭借的是经验。 下面再引出一道经典题目做一下分析:

第 2 页/共 50 页

信息学竞赛中的动态规划专题

ACM/ICPC Shanghai2001 Skiing http://122.139.62.222/problem.php?id=1862 【题目描述】 滑雪是一项很受欢迎的体育运动,为了获得速度,滑的区域必须向下倾斜,而且当你滑 到坡底,你不得不再次走上坡。我们想知道载一个区域中最长的滑坡。区域由一个二维数组 给出。数组的每个数字代表点的高度。下面是一个例子: 12345 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 我们可以从某个点滑向上下左右相邻四个点之一, 当且仅当高度减小。 在上面的例子中, 一条可滑行的滑坡为 24-17-16-1。当然 25-24-23-...-3-2-1 更长。事实上,这是最长的一条。 【输入格式】 输入的第一行表示区域的行数 R 和列数 C(1 <= R,C <= 500)。下面是 R 行,每行有 C 个 整数,代表高度 h,0<=h<=10000。 【输出格式】 输出最长区域的长度。 【样例输入】 55 12345 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 【样例输出】 25 有了前面的例子,不难看出,每个点可以由四个方向中比它高的点滑到。设 DX = {0,1,0,-1},DY = {1,0,-1,0},F[I,J]表示滑到第 I 行第 J 列的点时存在的最长滑坡长度,则有 状态转移方程: F[I,J] = Max{F[I+DX[K],J+DY[K]]}+ 1 ,其中要求满足第 I+DX[K] 行第 J+DY[K]列的点存在且高度比第 I 行第 J 列的点的高度高。我们可以按照深度优先搜索的方 式计算 F,并利用二维数组 Arr 记录计算过的 F 值,下面同样给出程序主干部分: Function F (Int I, Int J) { If Arr[I,J] > 0 Then
第 3 页/共 50 页

信息学竞赛中的动态规划专题

Return Arr[I,J] Int P, Ans = 0 For P = 1 to 4 Do If ((I+DX[P],J+DY[P]) In Map) And (H[I+DX[P],J+DY[P]] > H[I,J]) Then If (Ans < F[I+DX[P],J+DY[P]]) Ans = F[I+DX[P],J+DY[P]] Arr[I,J] = Ans + 1 Return Arr[I,J] } 同样是动态规划, 是什么使得两道题目代码的主干部分相差巨大呢?这里讨论一下动态 规划的两种实现形式——递推和记忆化搜索。 首先, 可以说所有用递推实现的动态规划均可 以利用记忆化搜索实现。 而某些题目之所以可以用递推求解, 是因为这类题目同一阶段的状 态表示上有很大的相关性, 比如数字矩阵中某一行或列, 这使得我们可以计算一个阶段的所 有状态后再计算下一状态。 而某些题目中利用动态规划划分的同一阶段的状态表示上没有多 大相关性,比如 Skiing 里面的状态,从某点做起点每滑动一步为一个阶段,我们无法用一 个准确的可以直接利用的集合将一个阶段中的状态表示出来, 只能从已知状态去找和它相关 联的状态。对于 Skiing 我们已知的是目标状态(即四面都不比该点高的点) ,通过边界条件 (即四面都比该点高的最优值为 1) ,便可以进行记忆化搜索。 利用递推实现动态规划时,单位操作时间小,可以方便地使用一些优化;而利用记忆化 搜索实现动态规划时,单位操作时间大,但可以避免计算一些不必要的状态。总地来说,相 比于用状态空间搜索的方法解决这类存在重复子问题的题目, 使用动态规划增大了空间的开 销,但提高了时间效率。 1.2 解决复杂贪心问题 接下来,进入下一话题。我们考虑一下我们熟知的贪心算法和动态规划的关系,我看过 很多写贪心算法和动态规划之间区别的材料, 在这里我们不谈这个, 而是要讨论动态规划与 贪心算法之间的联系。 如果我们把每一步贪心作为一个阶段, 那么可以认为每个阶段只有一个状态, 再把贪心 策略看作状态转移方程,那么这样是否也是一种“动态规划”呢?实际上,它们二者之间的 差别就在数据的维护上,有很多贪心问题在采取一次贪心策略之后要对数据进行全盘的维 护,而我们讲的动态规划一般没有这个步骤。 而这个维护的目的是什么呢?是为了保证正确性, 和动态规划中的最优子结构的目的一 样, 那么就说明目前的状态划分不具有最优子结构, 那么我们是否能够通过改变状态的划分 方法来代替这个维护并使新划分的状态具有最优子结构呢?这里直接给出结论: 对于某些分 步讨论的贪心决策问题,我们可以通过扩展状态使之能够用动态规划解决。扩展出的状态 的作用就是为了保证正确性,也就是保证最优子结构。 举一个简单的例子:给出 N 个数,要从其中取 M 个求和,并使和尽量大。这明显是一 个贪心可解的问题,把数字从大到小排序后取前 M 个求和即可。那么我们同样也可以扩展 出一部分状态。 我们设 F[I,J]表示前 I 个数字中取了 J 个数字得到的最大和, 则有: F[I,J] = Max (F[I–1,J],F[I-1][J-1] + A[J])。那些贪心算法并不用考虑的“多余”状态就是扩展出的状态, 举个实例来说明:N = 5 , M = 3 时,A[] = {1, 2, 3, 4, 5}。那么显然 1 和 2 都不会被取到,但 数组 F 中的 F[1,1], F[2,1] 和 F[2,2]都是由 1 和 2 组成的状态, 从贪心的角度看, 它们就是多 余的,就是为了使用动态规划扩展出来的状态。当然,就这道题目来看,贪心算法无论是从
第 4 页/共 50 页

信息学竞赛中的动态规划专题

思维角度、编程角度还是时空复杂度角度都明显优于动态规划。 HCPC Spring 2007 Hurdles Race http://acm.hit.edu.cn/hoj/problem/view?id=2476 【题目描述】 自从刘翔在雅典夺得 110 米栏冠军之后,国人对跨栏比赛的关注程度大大提高。 阿月和同学们经常在一起讨论刘翔需要用多少步来完成比赛, 大家对该问题的意见不太 一致,经常为此争论不休。 我们下面定义这样一种跨栏比赛: tl 表示起点到终点的距离(可能不是 110) ; sl 表示刘翔一步可以跨越的最大距离(我们规定刘翔每次跨越的距离必需是整数) ; fl 表示第一个栏到起点的距离(fl<tl) ; n 表示栏的数目; d 表示每两个栏之间的距离(我们保证最后一个栏到起点的距离小于 tl) ; 每次跨栏的时候,刘翔都要保证栏的位置恰好在他跨越距离的正中间。 求在这些条件下刘翔完成比赛所需要的最小步数。 【输入格式】 输入包括五个正整数,分别表示 tl,sl,fl,n,d(tl 不超过 10000,sl 不超过 10) 。 【输出格式】 输出包括一个整数,即刘翔完成比赛所需要的最小步数。 【样例输入】 110 3 20 10 5 【样例输出】 41 【样例说明】 起点到跨过第一个栏至少需要 8 步, 之后每跨一个栏至少需要 2 步, 从跨过最后一个栏 到终点至少需要 15 步。 由于只有跨栏的那步有限制条件, 其它步没有, 故有了贪心思想——跨栏那步要尽可能 的大。 通过分情况讨论后得到解: 跨第一个栏之前的步数 + 栏的个数 + 跑 2 个栏之间路程 需要的步数 ×(栏的个数 - 1) + 最后一个栏需要的步数。需要考虑的特殊情况只有跨第 一个栏的步长未必可以达到跨其它栏的步长。 当然,如果比赛的时候可以快速地想到这个方法是最好不过的。实际上,使用动态规划 更容易建立方程。 设 F[I]表示到达 i 位置所需要的最小步数, 则有 F[i]=min{F[I-K]+1}, K=1..sl, 其中 I-K 到 I 之间没栏;而有栏时,F[I]=min{F[I-2*sp]+1,F[I]},sp 为栏到 i 点距离。 AsyzOI2007 营养膳食 http://122.139.62.222/problem.php?id=1864
第 5 页/共 50 页

信息学竞赛中的动态规划专题

【题目描述】 阿月正在女朋友宁宁的监督下完成自己的增肥计划。 为了增肥,阿月希望吃到更多的脂肪。然而也不能只吃高脂肪食品,那样的话就会导致 缺少其他营养。 阿月通过研究发现: 真正的营养膳食规定某类食品不宜一次性吃超过若干份。 比如就一顿饭来说,肉类不宜吃超过 1 份,鱼类不宜吃超过 1 份,蛋类不宜吃超过 1 份,蔬 菜类不宜吃超过 2 份。 阿月想要在营养膳食的情况下吃到更多的脂肪, 当然阿月的食量也是 有限的。 【输入格式】 输入第一行包含三个正整数 n(n≤200),m(m≤100)和 k(k≤100) 。表示阿月每顿 饭最多可以吃 m 份食品,同时有 n 种食品供阿月选择,而这 n 种食品分为 k 类。第二行包 含 k 个不超过 10 的正整数,表示可以吃 1 到 k 类食品的最大份数。接下来 n 行每行包括 2 个正整数,分别表示该食品的脂肪指数 ai 和所属的类别 bi,其中 ai≤100,bi≤k。 【输出格式】 输出一个数字即阿月可以吃到的最大脂肪指数和。 【样例输入】 663 332 15 1 15 2 10 2 15 2 10 2 53 【样例输出】 60 用贪心算法解决, 就是把食品按脂肪指数排序后, 在满足约束条件的情况下从大的开始 吃,每吃一个更新一下约束条件。而用动态规划思想解决的话,可以设 F[I,J]表示前 I 类食 品一共吃 J 份能够获得的最大脂肪数和。则有 F[I,J] = Max {F[I-1,K] + G[I,J-K]},其中 G[I,J] 表示第 I 类食品种脂肪数最大的 J 份的和(也是要排序的) 。 Noip1999 旅行家的预算 http://122.139.62.222/problem.php?id=1523 【题目描述】 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空 的) 。给定两个城市之间的距离 D1、汽车油箱的容量 C(以升为单位) 。每升汽油能行驶的 距离 D2、出发点每升汽油价格 P 和沿途油站数 N(N 可以为零) ,油站 i 离出发点的距离 Di、每升汽油价格 Pi(i=l,2,...,N) 。
第 6 页/共 50 页

信息学竞赛中的动态规划专题

如果无法到达目的地,则输出“No solution” 。否则输出最小费用,计算结果四舍五入 至小数点后两位。 【样例输入】 275.6 11.9 27.4 2.8 2 1 102.0 2.9 2 220.0 2.2 【样例输出】 26.95 我们假设现在在第 I 站,那么可知在该站加满油可以到达的最远距离。如果在这个范围 内存在一个加油站 J,它的价格比 I 便宜,那么只要把油加到刚好能到达第一个出现的 J 即 可;否则就在 I 加满油,选择范围内最便宜的加油站 J,开到 J 再做决策。如果觉得这个方 法不是很好想的话,就用动态规划实现之。设 F[I,J]表示到达第 I 个加油站油量为 J 需要的 最小费用,则有 F[I,J] = Min {F[I-1, J-K-G(I-1,I)] + K*A[I]},其中 G(I-1,I)表示第 I 个加油站 和前一个加油站间的距离,A[I]表示第 I 个加油站的油价。 对于以上三道题目,实现贪心更容易,而想到动态规划更容易(前提是对动态规划足够 熟练) ,可以根据实际情况选择合适的算法。下面再给出两个相对复杂的题目。 AsyzOI2005 雇工 【题目描述】 一中搬到新校舍,值得庆祝。但我们亲爱的电教老师 FJ(Feng Jun not Farmer John)却 遇到了个麻烦事。科技馆还没完全建好,需要雇人来完成一些后续工作。现在的行情是这样 的:你雇佣一个人得给 A 元,解雇一个人得给人家 B 元(精神损失费) ,当然还有工资,每 月 K 元。有一系列工作,需要 N 月来完成。当然,不是每个月都需要相同的人数。可是当 你雇佣一个雇工,不管他干不干活,都得给他工资(吃大锅饭) 。说明一下:到期的时候是 不用付精神损失费的。 请你帮帮 FJ 老师,他心系学校,绝对要为一中省钱。 【输入格式】 输入包含三行。第一行为 N(不大于 12 的正整数) 。第二行有三个数,A,K,B (J 均不大于 100) 。第三行为每个月需要的最少人数(均小于 1000) 。 【输出格式】 输出包括一个数字即最小费用。 【样例输入】 3 456 10 9 11 【样例输出】
第 7 页/共 50 页

信息学竞赛中的动态规划专题

199 考虑每一个月,比较当前的工人数 M1 和下一个月所需要的工人数 M2,若 M1≤M2,则 必须雇佣缺少的工人,当然也不会多雇。问题的关键就在于可以解雇的时候解雇多少工人, 可以认为对于一组给定的 A,K 和 B 就可以得到一个吃大锅饭的最长时间(超过该时间可以 解雇了后再雇佣) ,这样我们找到这个时间内的最大工人需求量 M3,若 M1≤M3,那么不用 解雇任何工人,否则就要解雇 M1 - M3 个工人。需要注意的是,判断最长时间时需要考虑到 期的时候不付精神损失费的特殊情况。 而采用动态规划则要简单得多。设 F[I,J]表示完成了前 I 个月的工作任务且第 I 个月有 J 个工人所需的最小费用,则有 F[I,J] = Min {F[I-1,H] + G(H,J) + K*J},其中 G(H,J)表示由 H 个工人变化到 J 个工人所要支付的费用(或雇佣或解雇) 。使用动态规划来解决这道题目, 无论从思路还是实现来说都要比贪心算法简单。 在有规定时间限制的竞赛中, 做题的速度也很重要。 这催生了我们使用动态规划的第二 个动机——解决复杂的分步讨论的贪心决策问题。但仅限于数据范围不大的情况,因为较 比贪心算法,动态规划的时间复杂度要大一些。总地来说,这类动态规划牺牲了程序的时空 效率,但思维和编程比较简单,可以节约宝贵的竞赛时间。

第 8 页/共 50 页

信息学竞赛中的动态规划专题

2.动态规划的状态划分方法
在这里我们把动态规划状态的划分方法分为 3 种:一维状态划分、二维状态划分和树 型状态划分。树型动态规划是由于树这种数据结构的特殊性衍生出来的(放在最后说) ,这 里先讨论一下一维状态划分和二维状态划分的动态规划。 前面提到的动态规划基本都属于一维状态划分, 以 Number Triangles 的方程为例(F[I,J] 表示从顶层走到第 I 行第 J 列的点能取得的最大和) 。定义 I 为阶段变量,J 为状态变量(我 为了自圆其说,方便讲解,自己定义的) ,阶段变量可以确定状态所在阶段,而状态变量则 反映状态本身的性质。允许只有阶段变量没有状态变量,例如 Hurdles Race 里的 F[I]。而前 面提到的二维状态划分只有 Skiing 一题 (F[I,J]表示滑到第 I 行第 J 列的点时存在的最长滑坡 长度) ,因为这里 I 和 J 两个变量才能确定状态所在的阶段。 2.1.1 典型的线性动态规划 我们通常说的线性动态规划就是一维状态划分的没有状态变量的动态规划。 下面了列举 几个典型的线性动态规划题图: UVA 10684 The Jackpot 【题目描述】 某人想迅速变得富有,但是他还不想工作。于是他开始赌博,存在一个奖金序列(有正 有负) ,他想从中赢得最多的钱,我们规定他中途只可以退出一次(退出后不可以再回来) 。 【输入格式】 输入第一行包含一个正整数 N(N≤10000) ,接下里包含 N 个整数,它们的绝对值都不 超过 1000。 【输出格式】 输出该人能赢得的最大钱数。 【样例输入】 5 12 -4 -10 4 9 【样例输出】 13 我们称该类问题为最大连续数字和。设 F[I]表示到 I 为止(必须含 A[I])的最大连续整 数和,如果 F[I-1]为负数,那么显然 F[I] = A[I],否则有 F[I] = F[I-1] + A[I]。这样就构造出 一个线性动态规划算法了,以下是它的一个经典应用: NECPC2007 Sum Of SubRectangular Parallelepiped http://acm.hrbeu.edu.cn/index.php?act=problem&id=1229
第 9 页/共 50 页

信息学竞赛中的动态规划专题

【题目描述】 现有一个棱长为 n 的立方体,可以分成 n3 个 1*1*1 的单位立方体。每个单位立方体都 有一个整数值。 现在要求在这个立方体找到一个包含完整单位立方体的长方体, 使得该长方 体内所有单位立方体的数和最大。 【输入格式】 第一行包含一个整数 n。接下来 n 个 n2 的数字矩阵,每个数字矩阵代表一层,每个数字 代表一个单位立方体的整数值。 【输出格式】 输出仅包括最大的长方体的数和。 【样例输入】 2 12 21 -1 –2 -2 -1 【样例输出】 6 最基础的方法是“直译”枚举过程,时间复杂度 O(n9) 。而记录先前考察的结果。如 图所示,在统计长方体 2 时,只要将长方体 1 的统计结果加上长方体 3 就可以了,而不必按 上述算法那样重新进行计算。经过这样的优化, 利用了前面的计算结果,时间复杂度降为 O(n8) 。 而对于每个平面的矩形有一种经典的压缩方 法, 设 rec[x,y,z]表示 z 轴坐标为 z 的水平面中矩形 (1,1,x,y)的数和。则 z 轴坐标为 z 的水平面中左 上角为(x1,y1) 、右下角为(x2,y2)的矩阵的数 和为 rec[x2,y2,z] + rec[x1,y1,z] - rec[x2,y1,z] rec[x1,y2,z]。 有了上面的关系式,我们下面要做的只是枚举 z,x1,x2,y1,y2 来查找最优解。 对于每组固 定的 x1,x2,y1,y2, rec[z, x1,x2,y1,y2]就等于 z 个数字, 那么只要求它们的最大连续和就可以。 5 总的时间复杂度为 O(n ) 。 Noip2004 合唱队型

【题目描述】 N 位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的 K 位同学排成 合唱队形。 合唱队形是指这样的一种队形:设 K 位同学从左到右依次编号为 1,2?,K,他们的
第 10 页/共 50 页

信息学竞赛中的动态规划专题

身高分别为 T1,T2,?,TK,则他们的身高满足 T1<...<Ti>Ti+1>?>TK(1≤i≤K) 。 你的任务是,已知所有 N 位同学的身高,计算最少需要几位同学出列,可以使得剩下 的同学排成合唱队形。 【输入格式】 第一行是一个整数 N(2≤N≤106),表示同学的总数。第一行有 n 个整数,用空格分隔, 第 i 个整数 Ti(130≤Ti≤230)是第 i 位同学的身高(厘米)。 【输出格式】 只包含一个整数,就是最少需要几位同学出列。 【样例输入】 8 186 186 150 200 160 130 197 220 【样例输出】 4 首先只考虑左半部分的合唱队型,这种题目类型叫做最长上升子序列问题(LIS) ,最 常规的算法是设 F[I]表示前 I 个数字中(必须包含 A[I])的最长上升子序列的长度,状态转 移方程为 F[I] = Max {F[J] + 1},其中 J∈[0,I-1] 且 A[J] < A[I]。I 和 J 都需要枚举,所以时间 复杂度为 O(n2) 。 实际上 LIS 有一种贪心算法, 我们用数组 G[I]记录当前长度为 I 的上升子序列的最后一 个元素的最小值,那么 G[I]将会是一个单调的序列。对于每一个 A[J],只要在 G 序列中找 到一个最大的 I,使得 G[I] < A[J],那么就可以在它的后面插入 A[J]就形成了当前的最长上 升子序列,接下来需要更新 G(当然只是其中的一个元素) 。对于顺序表 G 的查找可以使用 二分查找,这样整个算法的时间复杂度为 O(nlogn) 。 另外值得一提的就是在解决合唱队型这个问题时, 不要枚举分割点之后再分别向两个方 2 向动态规划,那样的时间复杂度为 O(n logn) 。比较明智的做法是分别向两个方向动态规 划,再枚举分割点,直接做加法计算即可,时间复杂度为 O(nlogn) 。 2.1.2 其他线性动态规划举例 很多其他的线性动态规划基本都是大同小异, 它们的共同点就是沿着一个轴 (如坐标轴、 时间轴)进行规划;由于没有状态变量,它们的状态就是用 F[I]表示到轴上第 I 个点为止的 题目所要求的最优解。接下来再举两个例子加以说明。 USACO 3.1.2 Score Inflation http://122.139.62.222/problem.php?id=1441 【题目描述】 学生在我们 USACO 的竞赛中的得分越多我们越高兴。 我们试着设计我们的竞赛以便人们能尽可能的多得分,这需要你的帮助。 我们可以从几个种类中选取竞赛的题目, 这里的一个 “种类” 是指一个竞赛题目的集合, 解决集合中的题目需要相同多的时间并且能得到相同的分数。
第 11 页/共 50 页

信息学竞赛中的动态规划专题

你的任务是写一个程序来告诉 USACO 的职员,应该从每一个种类中选取多少题目,使 得解决题目的总耗时在竞赛规定的时间里并且总分最大。 【输入格式】 输入包括竞赛的时间,M(1≤M≤10,000)和 N, “种类”的数目(1≤N≤10,000) 。后面 的每一行将包括两个整数来描述一个“种类” ,第一个整数说明解决这种题目能得的分数(1 ≤points≤10000),第二整数说明解决这种题目所需的时间(1≤minutes≤10000) 。 【输出格式】 只包含一个整数,就是在竞赛的时间中得到最大的分数。 【样例输入】 300 4 100 60 250 120 120 100 35 20 【样例输出】 605 很容易写出线性动态规划方程:设 F[I]为到时间 I 为止任意安排题目可得的最多分数。 则 F[I] = Max {F[I-A[J]] + B[J]}, 其中 A[J]为第 J 类题目的时间, B[J]为第 J 类题目可得分数。 时间复杂度为 O(M N),在 1s 的时限内难以出解。 事实上,很多种类的题目是废题(用时多,得分少) 。我们可以用一些特殊的数据结构 找出这些废题,并不在动态规划的时候考虑它们,但我们也可以用性价比(得分/用时)来 大略地衡量某种题目的好坏。如果我们只取性价比最好的前 K 种题目,那么动态规划的时 间复杂度就为 O(MK)。实践证明,取 K = 150 时已经可以通过全部测试数据。 Noip2005 过河 http://122.139.62.222/problem.php?id=1571 【题目描述】 在河上有一座独木桥, 一只青蛙想沿着独木桥从河的一侧跳到另一侧。 在桥上有一些石 子,青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数,我们可 以把独木桥上青蛙可能到达的点看成数轴上的一串整点:0,1,??,L(其中 L 是桥的长 度) 。坐标为 0 的点表示桥的起点,坐标为 L 的点表示桥的终点。青蛙从桥的起点开始,不 停的向终点方向跳跃。一次跳跃的距离是 S 到 T 之间的任意正整数(包括 S,T) 。当青蛙跳 到或跳过坐标为 L 的点时,就算青蛙已经跳出了独木桥。 题目给出独木桥的长度 L,青蛙跳跃的距离范围 S,T,桥上石子的位置。你的任务是确 定青蛙要想过河,最少需要踩到的石子数。 【输入格式】 第一行有一个正整数 L(1≤L≤109) ,表示独木桥的长度。第二行有三个正整数 S,T,
第 12 页/共 50 页

信息学竞赛中的动态规划专题

M,分别表示青蛙一次跳跃的最小距离,最大距离,及桥上石子的个数,其中 1≤S≤T≤10, 1≤M≤100。第三行有 M 个不同的正整数分别表示这 M 个石子在数轴上的位置(数据保证 桥的起点和终点处没有石子) 。所有相邻的整数之间用一个空格隔开。 【输出格式】 只包括一个整数,表示青蛙过河最少需要踩到的石子数。 【样例输入】 10 235 23567 【样例输出】 2 看到题目首先想到的是时间复杂度为 O(TL)的线性动态规划。设 F[I]表示青蛙跳到 I 点 时所踩的最小石子数,则有 F[I] = Min{F[I-K] + A[I]}。但是 L 的上限为 109,这种算法显然 是不行的。仔细思考,可以得到下面的结论:存在 N0,当 n > N0 时,n 可以由若干 S 到 T 之间的正整数(包括 S,T)组成。因此,将障碍点按升序排列,当两相邻障碍点之间距离 较大时,可适当缩小两障碍点之间距离,但不影响最终结果。 (特别地,当 S=T 时需要单独 处理) 针对每一组 S 和 T 都存在一个 N0。对于任意的 S 和 T(S≠T 时) ,那么每次至少有 T 和 T-1 两种跳法。 假设青蛙跳 T 次,其中 K 次跳 T 步, T-K 次跳 T-1 步,那么总步数为 KT + (T-K)(T-1)= T(T-1) + K,也就是说 T(T-1)以外的所有点都可以跳到。这样一来,我们就可以 把间距超过 T(T-1) + K 的两点间距离化为 T(T-1) + K。T=K=10 时,T(T-1) + K 取得最大值 100,这时整个算法的时间复杂度为 O(100MT),可以在 1s 内通过全部测试数据。 2.1.3 一维状态划分的非线性动态规划 下面要讨论的是一维状态划分的非线性动态规划问题。 其中最为经典的模型就是 0-1 背 包问题:给定 N 种物品和一背包。物品 I 的重量是 WI,其价值为 VI,背包的容量为 C。选 择装入背包的物品,使得装入背包中物品的总价值最大,求这个最大价值。 每考虑一件物品为一个阶段,对于每一物品来说,都只有取和不取两种可能。那么设 F[I,J]表示考虑前 I 个物品取的总重量不超过 J 的最大价值, 则有状态转移方程: F[I,J] = Max (F[I-1,J], F[I-1,J-WI] + VI) 。实际上,0-1 背包问题和 Number Triangles 问题只是在做决策 时略有不同,前者考虑取或者不取,而后者考虑要走到左边还是右边。最后提醒一下,0-1 背包是一个 NP 问题, 时空复杂度均为 O (NW) , 当 W 的规模比较大时 (不是很过分的大) , 空间开销随之增大,我们可以利用滚动数组解决这一问题。由于动态规划的无后效性,我们 只需记录相邻的两个阶段的状态即可,这就是滚动数组的原理。 Noip2006 金明的预算方案 http://122.139.62.222/problem.php?id=1579 【题目描述】 金明今天很开心, 家里购置的新房就要领钥匙了, 新房里有一间金明自己专用的很宽敞
第 13 页/共 50 页

信息学竞赛中的动态规划专题

的房间。更让他高兴的是,妈妈昨天对他说: “你的房间需要购买哪些物品,怎么布置,你 说了算,只要不超过 N 元钱就行” 。今天一早,金明就开始做预算了,他把想买的物品分为 两类:主件与附件,附件是从属于某个主件的,下表就是一些主件与附件的例子: 主件 电脑 书柜 书桌 工作椅 附件 打印机,扫描仪 图书 台灯,文具 无

如果要买归类为附件的物品,必须先买该附件所属的主件。每个主件可以有 0 个、1 个 或 2 个附件。附件不再有从属于自己的附件。金明想买的东西很多,肯定会超过妈妈限定的 N 元。于是, 他把每件物品规定了一个重要度, 分为 5 等: 用整数 1~5 表示, 第 5 等最重要。 他还从因特网上查到了每件物品的价格(都是 10 元的整数倍) 。他希望在不超过 N 元(可 以等于 N 元)的前提下,使每件物品的价格与重要度的乘积的总和最大。 设第 j 件物品的价格为 v[j], 重要度为 w[j], 共选中了 k 件物品, 编号依次为 j1, j2, ??, jk,则所求的总和为: v[j1]*w[j1]+v[j2]*w[j2]+ ?+v[jk]*w[jk]。 (其中*为乘号) 请你帮助金明设计一个满足要求的购物单。 【输入格式】 第 1 行为两个正整数,用一个空格隔开: N 和 m, (其中 N(<32000)表示总钱数, m(<60)为希望购买物品的个数。 )从第 2 行到第 m+1 行,第 j 行给出了编号为 j-1 的物品 的基本数据,每行有 3 个非负整数 v ,p 和 q 。 (其中 v 表示该物品的价格(v<10000) ,p 表 示该物品的重要度(1~5) ,q 表示该物品是主件还是附件。如果 q=0,表示该物品为主件, 如果 q>0,表示该物品为附件,q 是所属主件的编号) 【输出格式】 只 有 一 个 正 整 数 , 为 不超 过 总 钱 数 的 物 品 的 价格 与 重 要 度 乘 积 的 总 和的 最 大 值 (<200000) 。 【样例输入】 1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 【样例输出】 2200 题目已经提示我们每个主件可以有 0 个,1 个或 2 个附件。那么考虑每套主件与附件的 组合,最多有 5 种处理方法:不取,主件,主件+附件 A,主件+附件 B 和主件+附件 A+附
第 14 页/共 50 页

信息学竞赛中的动态规划专题

件 B。设 F[I,J]表示前 I 种组合花费为 J 获得的最大重要度乘积和,则有: F[I,J] = Max ( F[I-1,J], F[I-1,J-V[I,0]]+V[I,0]*W[I,0], F[I-1,J-V[I,0]-V[I,1]]+V[I,0]*W[I,0]+V[I,1]*W[I,1], F[I-1,J-V[I,0]-V[I,2]]+V[I,0]*W[I,0]+V[I,2]*W[I,2], F[I-1,J-V[I,0]-V[I,1]-V[I,2]]+V[I,0]*W[I,0]+V[I,1]*W[I,1]+V[I,2]*W[I,2]) 还可以利用“每件物品都是 10 元的整数倍”的条件,总的时间复杂度为 O(NM) 。 NoiWC2007 Hotel 【题目描述】 有 N 个男人,M 个女人,其中有 C(1≤C≤M,N≤500)对夫妇要住房。现在有 P(P ≤500)个房子。每个房子有个费用 Ci 和床位 Bi(Bi≤5) 。住房有以下要求: 1.每个房子住的人数不能超过 Bi 2.一个房间住了夫妇,不能再住其他人。 3.不考虑夫妇情况下:一个房间住了男人后,不能再住女人。对女人也是一样。 求这 N+M 个人住房的最少费用。 【输入格式】 第 1 行为四个正整数,N,M,C 和 P。以下 P 行每行包含两个正整数 Ci 和 Bi。 【输出格式】 只有一个正整数,为这 N+M 个人住房的最少费用(longint 范围内) 。 【样例输入】 3224 30 4 20 1 10 2 20 2 【样例输出】 40 事实上我们可以发现按照第 2 条住房的夫妇数不会超过 1, 如果有 2 对夫妇那么可以交 换一下,在同样代价下反而能住更多人。这样我们可以枚举夫妇数(0 或者 1) ,这样就去掉 了夫妇的这个限制。 设 F[I,J,K]表示前 I 个房间安排好后, 还剩下 J 男 K 女的最小费用。 则显然有 F[I,J,K]=Min {F[I-1,J,K], F[I-1,J+B[I],K]+C[I], F[I-1,J,K+B[I]]+C[I]},时间复杂度为 O(P M N)。和前面说 过的 Score Inflation 一样,在人数比较多的时候可以加入贪心思想。当人数超过 R 的时候, 性价比比较高的房间就必然会被使用, 那么先把所有房间按照性价比排序然后按顺序分放直 到人数少于 R 为止,时间复杂度就降为 O(P R2)。 Shanghai2004 The Horse Racing
第 15 页/共 50 页

信息学竞赛中的动态规划专题

http://122.139.62.222/problem.php?id=1865 【题目描述】 中国古代的历史故事“田忌赛马”是为大家所熟知的。话说齐王和田忌又要赛马了,他 们各派出 N 匹马(N≤2000) ,每场比赛,输的一方将要给赢的一方 200 两黄金,如果是平 局的话,双方都不必拿出钱。现在每匹马的速度值是固定而且已知的,而齐王出马也不管田 忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马,才能赢最多的钱?

【输入格式】 第 1 行为一个正整数 N。第 2 行和第 3 行每行包含 N 个正整数,分别表示田忌和齐王 帐下马的速度。 【输出格式】 只有一个正整数,即田忌能赢得的最大钱数。 【样例输入】 3 92 83 71 95 87 74 【样例输出】 200 这个问题很显然可以转化成一个二分图最佳匹配的问题。 把田忌的马放左边, 把齐王的 马放右边。田忌的马 A 和齐王的 B 之间,如果田忌的马胜,则连一条权为 200 的边;如果 平局,则连一条权为 0 的边;如果输,则连一条权为-200 的边,但二分图最佳匹配算法的 复杂度为 O(N3) 。 因为田忌掌握有比赛的主动权, 他总是根据齐王所出的马来分配自己的马, 所以这里不 妨设齐王的出马顺序是按马的速度从高到低出的。 对于这样的假设,我们归纳出如下贪心策略: ? 1.如果田忌剩下的马中最强的马都赢不了齐王剩下的最强的马, 那么应该用最差的一匹 马去输给齐王最强的马; ? 2.如果田忌剩下的马中最强的马可以赢齐王剩下的最强的马,那就用这匹马去赢齐王剩 下的最强的马; 这两点是显然的, 关键在于田忌最快的马和齐王最快的马打平, 那么田忌是选择平还是 输呢? ? 如果全部打平的话,如果齐王马的速度分别是 1 2 3,田忌马的速度也是 1 2 3,每次选
第 16 页/共 50 页

信息学竞赛中的动态规划专题

择打平的话,田忌一分钱也得不到,而如果选择先用速度为 1 的马输给速度为 3 的马的话, 可以赢得 200 两黄金。而如果全部输掉的话,如果齐王马的速度分别是 1 3,田忌马的速度 分别是 2 3,田忌一胜一负,仍然一分钱也拿不到。而如果先用速度为 3 的马去打平的话, 可以赢得 200 两黄金。 这里虽然出现了分支, 但我们得知田忌一定是将他马按速度排序之后, 从两头取马去和 齐王的马比赛。那先把田忌和齐王的马分别按从强到弱排序,设 F[I,J]表示齐王按从强到弱 的顺序出马和田忌进行了 I 场比赛之后,田忌从头取了 J 匹较强的马出战所能够得到的最大 钱数。则有:F[I,J] = Max {F[I-1,J] + G[N-(I-J)+1,I],F[I-1,J-1]+G[J,I]},其中 G[J,I]表示田忌的 第 J 匹马和齐王的第 I 匹马比赛的获利。 2.1.4 压缩状态的动态规划 下面介绍一下压缩状态的动态规划。 这种动态规划的本质是对集合进行动态规划, 对于 给出的数据在某一个或几个维度上一般具有比较小的范围(可以枚举一类的状态) ,我们把 一个枚举出的状态视为一个集合,通过它们之间的关系(产生式规则)可以进行动态规划。 当集合中元素个数的不定性或范围大时, 如果直接开数组存, 索引数组的编程复杂度太 高(而且程序时间效率低下) ,所以要进行集合编码。一般利用数据的可枚举性,采用进位 制的方法进行状态压缩。下面举一个经典的问题作为例子: Noi2001 炮兵阵地 【题目描述】 司令部的将军们打算在 N*M 的网格地图上部署他们的炮兵部队。一个 N*M 的地图由 N 行 M 列组成,地图的每一格可能是山地(用"H" 表示) ,也可能是平原(用"P"表示) ,如 下图。在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队) ;一 支炮兵部队在地图上的攻击范围如图中黑色区域所示:

如果在地图中的灰色所标识的平原上部署一支炮兵部队, 则图中的黑色的网格表示它能 够攻击到的区域:沿横向左右各两格,沿纵向上下各两格。图上其它白色网格均攻击不到。 从图上可见炮兵的攻击范围不受地形的影响。 现在,将军们规划如何部署炮兵部队,在防止误伤的前提下(保证任何两支炮兵部队之 间不能互相攻击,即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内) ,在整个地图 区域内最多能够摆放多少我军的炮兵部队。 【输入格式】 第一行包含两个由空格分割开的正整数,分别表示 N 和 M;
第 17 页/共 50 页

信息学竞赛中的动态规划专题

接下来的 N 行,每一行含有连续的 M 个字符('P'或者'H'),中间没有空格。按顺序表示 地图中每一行的数据。N≤100;M≤10。 【输出格式】 仅一行,包含一个整数 K,表示最多能摆放的炮兵部队的数量。 【样例输入】 54 PHPP PPHH PPPP PHPP PHHP 【样例输出】 6 这是一道比较麻烦的问题,如果某点是 P,就可以有放兵与不放兵两种方案,但对于在 I 和 J 位置之前的所有 P 的摆放方案有多种方案, 我们将这两种方案分别去尝试与 P(I,J)之前 所有方案结合,则 P(I,J)又会有很多种方案。 考虑一个列为 10(M 的最大值)的表。即使是一个全为 P 的空列上一共也只有 60 种合 法的炮兵放置方法。具体对一个列数为 10 的 PH 表而言,对每一列也只有前两列对其产生 影响,我们设 F[I,X,Y]来表示第 I-1 行处于第 X 种状态,第 I 行处于第 Y 种状态时,从首行 扫描到该行时所能存放的最多的炮兵数。 则有 F[I,X,Y] = Max{F[I-1,Z,X] + N[Y]}, 其中要求 没有互相攻击的可能,N[Y]表示方案 Y 对应的炮兵数。 很多状态压缩动态规划是用二进制存储状态, 比如有 1 到 10 共 10 个点, 需要把它们都 走一遍,走过 1,2,3 点的路径可以用[0000000111]2=[7]10 表示,而走过 1,2,3,5 的路径可以用 [0000010111]2=[23]10 表示。下面我们用位运算建立它们之间的联系,需要使用异或运算符 (^) ,[0000010111]2^[0000010000]2=[0000000111]2,即 23^(1<<(5-1)) = 7,这大大方便了我 们在状态压缩动态规划中进行状态转移。下面再举一个例子: HCPC Spring 2007 FishCanFly 【题目描述】 fish is not a common fish, he has a dream that he can fly someday. One day his friend wolfshow tells him a tale. "It is said that there lives a magic bailey in the remote mountains. He can enable some fish to fly once a year. Every year many fish arrive at bailey's house. The lucky fish is the one who has the highest score(what a bad thing!). There are several posthouses on the way to bailey's house. One can get some score when he enters it. But if you enter the same posthouse several times, you can get the score only once. You must remember that the total time is limited. So if you can't get there in time, you will lose it." Luckily, with another friend angela's help, fish gets the map. But he can't calculate the travel
第 18 页/共 50 页

信息学竞赛中的动态规划专题

path that makes him the lucky fish. Fortunately, you are kind enough to help him, and what you need only to do is the calculation. 【输入格式】 Each test case starts with a single integer n (2 <= n <= 11) denoting the number of posthouses. The posthouses are numbered from 1 to n. Then a matrix with n+2 rows and n+2 columns followes. The integer in row i(row j) and column j(column i) is the time fish will cost to travel between place i and place j directly. A zero means that there is not a direct way connecting place i and j. fish starts with place 0 and bailey's house is at place n+1. The next line contains n integers which indicate the scores at each posthouse. Then followes an integer number denoting the time limit. 【输出格式】 If fish can arrive at bailey's house in time, please output "Fish can fly!" and the highest score he can get separated by just one space. If he can't arrive in time no matter which path he takes, just ouput "Miss bailey!". See the examples for further clarification. 【样例输入】 3 02000 20300 03081 00800 00100 123 【样例输出】 Fish can fly! 6 首先利用 Floyed 求出最短路, 然后进行状态压缩的动态规划。 设 F[I,S]表示在第 I 个点, 经过路径为 S 的最少时间,则有: F[I,S] = Min {F[J,S^(1<<I)] + D[I,J]} 其中 J=1..N 且 (1>>J)&(S^(1<<I)) == 1。最后在规定时间内的路径中选择一条分数最高的,时间复杂度为 O (N2N) 。 2.2.1 典型的二维状态划分的动态规划 下面我们开始讨论二维状态划分的动态规划, 这类题目需要使用两个变量确定一个状态 的阶段。首先介绍一个经典问题:最长公共子序列(LCS) 。将两个给定字符串分别删去零 个或多个字符后得到的长度最长的相同字符序列。 例如, 字符串 abcabcabb 与 bcacacbb 的最 长公共子序列为 bcacabb。LCS 问题就是要求两个给定字符串的最长公共子序列的长度。 我们每考虑一个相同的字母为一个阶段, 对于每一个相同的字母来说, 都可以在它以前 最大长度的基础上加 1。F[I,J]表示第 1 个字符串前 I 个字符和第 2 个字符串前 J 个字符的最 长公共子序列的长度,则有状态转移方程: F[I,J] = F[I-1,J-1] + 1, 其中 A[I] = B[J];
第 19 页/共 50 页

信息学竞赛中的动态规划专题

F[I,J] = F[I-1,J-1], 其中 A[I] <> B[J]; 计算 LCS 长度的时间复杂度: O (LEN_A· LEN_B) , 构造 LCS 的时间复杂度: O (LEN_A + LEN_B) 。 Ioi2000 Palindrome http://122.139.62.222/problem.php?id=1866 【题目描述】 回文词是一种对称的字符串——也就是说, 一个回文词从左向右读和从右向左读得到的 结果是一样的。任意给定的一个字符串,通过插入若干字符,都可以变成一个回文词。你的 任务是求出将给定字符串变成回文词所需要插入的最少字符数。 【输入格式】 第一行包含一个数字 N(N≤5000) ,表示字符串的长度,第二行包含一个长度为 N 的 字符串。 【输出格式】 只有一个正整数,为将给定字符串变成回文词所需要插入的最少字符数。 【样例输入】 5 Ab3bd 【样例输出】 2 这个问题相当于把将原串从某点截成两段,求前一段与后一段的逆串的最长公共子序 列。和合唱队型类似,不要先枚举分割点,将原串和其逆串的最长公共子序列的最长公共子 序列计算之后再做分割处理。 我们前面提到过 LIS,现在又介绍了 LCS,下面讨论一下它们的结合体:最长公共上升 子序列(LCIS) 。对于 LCIS 的定义如下: 给出两个长度分别为 n,m 的序列 A 和 B。求出一个长度最长序列 C,满足: C1 < C2 < ?? < Cl; C 既是 A 的子序列又是 B 的子序列; 最直接的方法就是设 F[I,J]表示 A1 到 AI 和 B1 到 BJ 的 LCIS 的长度,其中 AI = BJ,那么 有 F[I,J] = Max {F[P,Q] +1},其中P= 1..I-1,Q = 1..J-1,AP=BQ,AP>AI 且 BQ>BJ。该算法的 时间复杂度为 O(N4) 。 为了提高算法效率,我们需要去掉一些重复计算,例如上述算法中存在 L 使BL<BJ1,BJ2 且 L<J1,J2,那么在计算F[I,J1]和 F[I,J2]时,F[K,L](K = 1..I-1)被枚举了两次来取最大值。 实际上计算某个状态集合, 其实质是计算这个集合中状态值最大的状态, 因此我们只需知道 这个集合中的最大状态值就足够了。那么不妨设 G[I,L] = Max {F[K,L]},其中 K = 1..I,于 是得出双状态的状态转移方程: F[I,J] = Max {G[I-1,K] +1};
第 20 页/共 50 页

信息学竞赛中的动态规划专题

G[I,J] = Max (G[I-1,J], F[I,J]); 这时算法的时间复杂度为 O(N3) ,而 LCIS 有 O(N2)的算法,由于其过于复杂这里 暂不做相关介绍。 另外一个经典的二维状态划分的动态规划为矩阵乘法,而 OIers 则更习惯称之为石子和 并或者最小代价子母树。现在考虑下面这道题目: Noip2006 能量项链 http://122.139.62.222/problem.php?id=1578 【题目描述】 在 Mars 星球上,每个 Mars 人都随身佩带着一串能量项链。在项链上有 N 颗能量珠。 能量珠是一颗有头标记与尾标记的珠子,这些标记对应着某个正整数。并且,对于相邻的两 颗珠子,前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样,通过吸盘(吸 盘是 Mars 人吸收能量的一种器官)的作用,这两颗珠子才能聚合成一颗珠子,同时释放出 可以被吸盘吸收的能量。如果前一颗能量珠的头标记为 m,尾标记为 r,后一颗能量珠的头 标记为 r,尾标记为 n,则聚合后释放的能量为(Mars 单位) ,新产生的珠子的头标记为 m, 尾标记为 n。 需要时,Mars 人就用吸盘夹住相邻的两颗珠子,通过聚合得到能量,直到项链上只剩 下一颗珠子为止。显然,不同的聚合顺序得到的总能量是不同的,请你设计一个聚合顺序, 使一串项链释放出的总能量最大。 例如:设 N=4,4 颗珠子的头标记与尾标记依次为(2,3) (3,5) (5,10) (10,2)。我们 用记号⊕表示两颗珠子的聚合操作,(j⊕k)表示第 j,k 两颗珠子聚合后所释放的能量。则第 4、1 两颗珠子聚合后释放的能量为: (4⊕1)=10*2*3=60。 这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 ((4⊕1)⊕2)⊕3)=10*2*3+10*3*5+10*5*10=710。 【输入格式】 第一行是一个正整数 N(4≤N≤100) ,表示项链上珠子的个数。第二行是 N 个用空格 隔开的正整数, 所有的数均不超过 1000。 第 i 个数为第 i 颗珠子的头标记 (1≤i≤N) , 当 i<N< span>时,第 i 颗珠子的尾标记应该等于第 i+1 颗珠子的头标记。第 N 颗珠子的尾标记应该 等于第 1 颗珠子的头标记。 至于珠子的顺序,你可以这样确定:将项链放到桌面上,不要出现交叉,随意指定第一 颗珠子,然后按顺时针方向确定其他珠子的顺序。 【输出格式】 只有一个正整数 E(E≤2.1*109) ,为一个最优聚合顺序所释放的总能量。 【样例输入】 4 2 3 5 10 【样例输出】 710
第 21 页/共 50 页

信息学竞赛中的动态规划专题

记 A[I]为第 I 颗能量珠的首标记,也同时是它前面那颗能量珠的尾标记。设 F[I,J]为从 以 A[I]为首标记的能量珠开始顺时针数到以 A[J]为尾标记的能量珠为止所有能量珠组成的 串合并后放出的最大能量。则有:F[I,J]=Max{F[I,K]+F[K,J]+A[I] *A[K]*A[J]} (K= I ..J)。 计算 F[I,J]时,只会用到含有能量珠数目比它少的串在数组中的值,所以要按照串的能 量珠数目依次增大的顺序递推。接下来,如果解决环的问题呢?枚举分割点是一种办法,但 是会把时间复杂度增加到 O(N4) 。所以我们不如将原串复制一份加到原串的后面再进行动 态规划。 HLJCPC 2007 Max http://acm.hrbeu.edu.cn/index.php?act=problem&id=1218 【问题描述】 给出一个表达式请你添加一些括号使最后的结果尽可能的大,比如下面的表达式: 1+2*3 直接看的结果是 7,然而如果添加一个括号,如(1 + 2) * 3,那么它的结果就是 9 了。实 际上,9 也是最大的结果。 【输入格式】 第一行是一个正整数 N(2≤N≤100) ,第二行是一个表达式,只包含*和+两种运算符, N 个数字间有 N-1 个运算符,其中数字可以为负数。 【输出格式】 只有一个正整数即表达式可以到达的最大值。 【样例输入】 4 1 + 2 * 3 + -1 【样例输出】 8 题目的做法基本和矩阵乘法一致,但是需要注意一点:由于乘法运算的存在(两个最小 负数的乘积可能成为最大值) ,我们不仅要保存某部分表达式的最大值,还要保存它的最小 值。设 F[I,J]表示表达式从 I 到 J 部分的最大值,G[I,J] 表示表达式从 I 到 J 部分的最小值, 则有: Sign[i] = ?*?时 F[I,J] = Max{F[I,K] * F[K+1,J], G[I,K] * F[K+1,J], F[I,K] * G[K+1,J], G[I,K] * G[K+1,J]} G[I,J] = Min{F[I,K] * F[K+1,J], G[I,K] * F[K+1,J], F[I,K] * G[K+1,J], G[I,K] * G[K+1,J]} Sign[i] = ?+?时 F[I,J] = Max{F[I,K] + F[K+1,J]} G[I,J] = Min{G[I,K] + G[K+1,J]} AsyzOI 2005 龙珠外挂

第 22 页/共 50 页

信息学竞赛中的动态规划专题

【问题描述】 QQ 龙珠是腾讯公司新推出的一个 QQ 游戏项目。目的是为了有效的防止外挂,毕竟这 个游戏不是那么的简单。 QQ 龙珠的规则是这样的: 有一串 n 个带颜色的球 (最多可能有红、 黄、蓝和绿四种颜色) ,你可以向这个串里加球,当有连续三个或三个以上相同颜色的球连 在一起时, 我们称为可消除状态, 通过一次加球新产生出的可消除状态才真正意义上的可消 除。我们为了开发外挂,要找一个加入尽可能少的球并能将整串球全部消除的方案。 举个 n=12 的时候的例子,整个串的消除过程如下:

第一步,在第四个球前加入一个蓝色球;

第二步,在第八个球前加入一个蓝色球;

第三步,在第八个球前加入一个蓝色球;

第四步,在第二个球前加入一个绿色球; 第五步,在第二个球前加入一个绿色球; 第六步,在第一个球前加入一个红色球。这样就把整个串消除了,当然,方法不唯一。 【输入文件】 输入的第一行是一个整数 n(1 ≤ n ≤ 100) ,表示初始的球数。第二行有一个由 n 个字 符组成的字符串,每个字符只可能是 R(红)Y(黄)B(蓝)G(绿)其中的一个。 【输出文件】 输出包括一个整数 k,表示消除整个串最少需要放入 k 个球。 【样例输入】 12 RGRRRYBYYRBB 【样例输出】 6 未解决,- -!,求教 ww 大牛。 2.2.1 其他二维状态划分的动态规划举例 Central European 2000 I-KeyBoard http://acm.hit.edu.cn/hoj/problem/view?id=1042 【问题描述】 移动电话用户都对使用电话键盘输入英文短消息感到烦透了。 有时你真的没有心情输入
第 23 页/共 50 页

信息学竞赛中的动态规划专题

长一点儿的信息, 因为通常要按一个数字键好几下才能输入一个字母! 这都归咎于数字键太 少——典型的电话键盘只有 12 个键,更糟的是只有其中 8 个可以用来输入 26 个英文字母, 它的设计如下面的图所示。

每个键可以对应一组字母。 如果你想输入某一组的第 1 个字母, 你按一下对应的键就行 了;如果你要第 2 个,那你得按两下;如果是第 3 个或者第 4 个??这种键盘的设计者并不 在乎你按键次数的多少,他们只看重平均分配字母。有些字母的使用频率要高些,但它们被 安排在一组字母的第 3 个或第 4 个。例如 S 是个常用的字母,但我们要按 4 下才能输入一 个 S。 而我们需要你编写一个程序,找到一种最优的键盘(对于给定的字母使用频率) 。当然, 不论如何安排字母和按键的对应关系都必须保持字母的顺序, 这样用户才不会感到头晕。 不 过你可以安排任意数量的字母对应一个按键。 【输入文件】 输入第一行有两个整数 K 和 L(1 ≤ K ≤ L) 。K 表示提供按键的个数,L 表示有多少 字符需要安排到键盘上。接下来 L 行,每行是一个非负整数,这些数字依次表示字母表中 字符的使用频率。较大的数字表示较高的使用频率。这些数字最大不超过 10000。 【输出文件】 输出包括一个整数 S。S 为所有字符的输入代价和的最小可能值,一个字符的输入代价 定义为其使用频率与输入这个字母需要的按键次数的乘积。 一定要注意: 所有字母在键盘上 的排列顺序是不能改变的。 【样例输入】 8 26 3371 589 1575 1614 6212 971 773 1904
第 24 页/共 50 页

信息学竞赛中的动态规划专题

2989 123 209 1588 1513 2996 3269 1080 121 2726 3083 4368 1334 518 9999 427 733 871 【样例输出】 87180 显然地, 设 F[I,J]表示前 I 个键盘存有前 J 个字母的最小代价和, 则有: F[I,J] = Min{F[I-1,K] + G[K + 1,J]},其中 G[K + 1,J]表示把第 K+1 个字母到第 J 个字母存在一个键上的最小代价 和。数组 G 需要递推,总体算法的时间复杂度为 O(N3) 。 USACO Jan2007 Problem Solving http://122.139.62.222/problem.php?id=1867 【问题描述】 这些日子, FJ 的奶牛一共有 P (1 ≤ P ≤ 300) 个待解决的问题。 奶牛现在是上班族了, 每个月的工资为 M (1 ≤ M ≤ 1000) 。 奶牛现在需要雇人来解决那些问题, 其中有一个专家非常可靠, 可以每一个月解决一个 问题。他的收费方式是这样子的:解决问题前后各付一次钱( 1 ≤ payment ≤ M ) ,当然 奶牛必须在当时能够支付足够的钱。求解决这些问题所需要的最小时间。还有一点:这些问 题是有严格先后顺序的。 【输入格式】 第一行是两个正整数 M 和 P,以下 P 行每行两个数,表示解决该问题前后分别需要付 的费用。 【输出格式】 只有一个正整数即解决全部问题需要的最小月份数。

第 25 页/共 50 页

信息学竞赛中的动态规划专题

【样例输入】 100 5 40 20 60 20 30 50 30 50 40 40 【样例输出】 6 【样例说明】 +------+-------+--------+---------+---------+--------+ | | Avail | Probs | Before | After | Candy | |Month | Money | Solved | Payment | Payment | Money | +------+-------+--------+---------+---------+--------+ | 1 | 0 | -none- | 0 | 0 | 0 | | 2 | 100 | 1, 2 | 40+60 | 0 | 0 | | 3 | 100 | 3, 4 | 30+30 | 20+20 | 0 | | 4 | 100 | -none- | 0 | 50+50 | 0 | | 5 | 100 | 5 | 40 | 0 | 60 | | 6 | 100 | -none- | 0 | 40 | 60 | +------+-------+--------+---------+---------+--------+ 设 F[X,Y]表示解决前 X 个问题且最后一个月解决了 Y 个问题所需要的最小月份数。利 用辅助数组 G1[X,Y]和 G2[X,Y]表示在一个月解决问题 X 到问题 Y 间所有问题前后需要支 付的费用。则有状态转移方程:F[I,J] = Min {F[K][I-1] + P[I,J,K]},其中 G1[I,J] + G2[K,I-1] 不超过 M 时,P[I,J,K] = 1,否则 P[I,J,K] = 2。这种算法的时间复杂度为 O(N3) 。 和 LIS 一样,可以加入贪心思想,如果设 F[X]表示解决前 X 个问题需要的最小月份数, 同时用辅助数组 G[X]表示解决前 X 个问题取得最小月份时,该月最少花费的钱数。则有状 态转移方程:F[I] = Min{F[J] + Q[J,I,G[X]]},并随时更新 G[X],则把时间复杂度降到了 O (N2) 。 2.3 树型状态划分的动态规划 顾名思义,树型状态划分的动态规划就是在“树”的数据结构上的动态规划。由树的结 构可知,树型动态规划的方向一般是叶到根:将根的子节点传递有用的信息给根,使根得 出最优解。 URAL1039 Anniversary http://122.139.62.222/problem.php?id=1849 【问题描述】 有个公司要举行一场晚会。 为了能玩得开心,公司领导决定:如果邀请了某个人,那么一定不会邀请他的上司
第 26 页/共 50 页

信息学竞赛中的动态规划专题

(上司的上司,上司的上司的上司??都可以邀请) 。 每个参加晚会的人都能为晚会增添一些气氛,求一个邀请方案,使气氛值的和最大。 【输入格式】 第 1 行一个整数 N(1≤N≤6000)表示公司的人数。 接下来 N 行每行一个整数。第 i 行的数表示第 i 个人的气氛值 x(-128≤x≤127)。 接下来每行两个整数 L,K。表示第 K 个人是第 L 个人的上司。 输入以 0 0 结束。 【输出格式】 只有一个数,最大的气氛值和。 【样例输入】 7 1 1 1 1 1 1 1 13 23 64 74 45 35 00 【样例输出】 5 设 F[I]表示邀请 I 的最大值,G[I]表示不邀请 I 的最大值。则 F[I] = ∑{G[I.sons]},G[I] = ∑{Max(F[I.sons],G[I.sons]}}。大多的树型动态规划可以化成类似的类型,下面介绍一下多 叉树改造为二叉树的方法。 Ctsc1997 选课 http://122.139.62.222/problem.php?id=1290 【问题描述】 在大学里每个学生,为了达到一定的学分,必须从很多课程里选择一些课程来学习,在 课程里有些课程必须在某些课程之前学习, 如高等数学总是在其它课程之前学习。 现在有 N 门功课,每门课有个学分,每门课有一门或没有直接先修课(若课程 a 是课程 b 的先修课即 只有学完了课程 a,才能学习课程 b) 。一个学生要从这些课程里选择 M 门课程学习,问他 能获得的最大学分是多少?
第 27 页/共 50 页

信息学竞赛中的动态规划专题

【输入格式】 第一行有两个整数 N,M 用空格隔开。(1≤N≤200,1≤M≤150) 接下来的 N 行,第 I+1 行包含两个整数 ki 和 si, ki 表示第 I 门课的直接先修课, si 表示第 I 门课的学分。若 ki=0 表示没有直接先修课(1≤ki≤N, 1≤si≤20) 。 【输出格式】 只有一行,选 M 门课程的最大得分。 【样例输入】 74 22 01 04 21 71 76 22 【样例输出】 13 以样例数据为例,很容易建出一棵树(如右图所示) 。 我们可以选取某一个点 K 的条件只是它的父节点已经 被选取或者它自己为根节点;而且我们不论如何取 K 的子 孙节点,都不会影响到它父节点的选取情况,这满足无后效性原则。我们用函数 F[I,J]表示 以第 I 个节点为父节点,取 J 个子节点的最佳代价,则可以进行动态规划。可是如此规划, 其效率与搜索毫无差别。 我们不妨改造树,将其转变为二叉树。变化方法为:一 个节点的第一个孩子为其左孩子, 而一个节点的兄弟为其右 孩子。以样例数据为例,建出一棵二叉树(如右图所示) 。 转化的时间复杂度为 O (N) 。 我们还是利用同样的状态 表示方法,则有状态转移方程: F[I,J] = Max(F[L,K] + F[R,J-K-1] + S[I], F[R,J]) 整个算法的时间复杂度为 O(N3) 。 在实现树型动态规划的时候,通常使用后序遍历。

第 28 页/共 50 页

信息学竞赛中的动态规划专题

3.动态规划的辅助与优化方法
3.1.1 填鸭 这里说的填鸭通常也被视为动态规划,我们先来看一个经典的硬币问题:给出 N 种硬 币的面值,问面值 M 有多少种不同的表示方法。 我们常见的解法就是设 F[I]表示面值为 I 的不同表示方法,则 F[I] = ∑F[I-Cost[J]]。这 种填鸭没有决策,就是开一个大的数组,把代价值一个一个地填进去。 再举一个简单的游戏——步步为零。 游戏者在一张菱形的表格中按照规则跳动, 使得跳 到的数字经过加号和减号的连接,尽可能的逼近零。游戏者从最下面的方格出发,按照每次 可以往上面左右两个格子的任意一格跳动,当游戏者跳到最顶端的方格时,游戏结束。在游 戏未结束前,游戏者不允许跳到表格外。

2 31 -3 5 7 6 10 -2 20 -7 -5 –8 10 8 7
对于上面的表格,最好的跳动方案是:7+8+(-5)+(-2)-5-1-2=0 或 7+10+(-7)-6+(-3)-3+2=0 或 7+10+(-5)-10-5+1+2=0 或 7+10+(-5)+(-2)-5-3-2=0。 利用填鸭的方法,设 F[I,J,K]表示到第 I 层第 J 个数字组成 K 的可能性,则有 F[I,J,K] = F[I + 1,J - 1,K + A[I,J]] or F[I + 1,J - 1,K - A[I,J]] or F[I + 1,J,K + A[I,J]] or F[I + 1,J,K - A[I,J]]。 Oibh2005 胖子三角 【问题描述】 最近,地球上兴起了一股“登月热” 。人们纷纷报名参加太空游。胖子----这个摩登青年 当然不会落伍。现在,胖子乘神州 X 号来到月球,准备开辟一片新的天地。他在月球上建 立了一个食堂,并且想给他的月球食堂建造一个围栏。路人皆知的是胖子很爱吃,而且胖子 很虚荣,为了使围栏看起来很酷,而且很像麦当劳的珍宝三角,胖子决定用面包把它建成三 角形。 胖子现在拥有 N(3<=N<40)块面包, 由于胖子在建造围栏时不由自主地吃掉了一部分, 所以这些面包长短不一,但胖子还算有些人性,将每块长度都吃成了整数,经过 alston 锐利 的目光推测,将每块面包长度(1<=L<40)看出,为天文学爱好者带来极大方便。由于胖子的 占有欲一般都很强(特别是对食物),所以他还想用所有的面包使围栏的面积最大。 【输入格式】 第一行有一个整数 N,第二行有 N 个数,表示面包的长度。 【输出格式】 只有一个数,即最大面积,保留两位小数。
第 29 页/共 50 页

信息学竞赛中的动态规划专题

【样例输入】 3 435 【样例输出】 6 每一个面包可以被包含在三条边中的任意一条边中, 设 F[I,J,K]表示用前 I 个面包组成一 条长度为 J 的边和一条长度为 K 的边的可能性,则有状态转移方程:F[I,J,K] = F[I-1,J-AI,K] or F[I-1,J,K-AI]。最后枚举一下组成的可能所有三角型,取其中面积最大的。总的时间复杂 度为 O(N3L2) 。 NEYCoi 2003 搭建双塔 【题目描述】 2001 年 9 月 11 日,一场突发的灾难将纽约世界贸易中心大厦夷为平地,Mr. F 曾亲眼 目睹了这次灾难。为了纪念“9.11”事件,Mr. F 决定自己用水晶来搭建一座双塔。 Mr. F 有 N 块水晶, 每块水晶有一个高度, 他想用这 N 块水晶搭建两座有同样高度的塔, 使他们成为一座双塔,Mr. F 可以从这 N 块水晶中任取 M(1≤M≤N)块来搭建。但是他不 知道能否使两座塔有同样的高度, 也不知道如果能搭建成一座双塔, 这座双塔的最大高度是 多少。所以他来请你帮忙。 给定水晶的数量 N(1≤N≤100)和每块水晶的高度 Hi(N 块水晶高度的总和不超过 2000) ,你的任务是判断 Mr. F 能否用这些水晶搭建成一座双塔(两座塔有同样的高度) ,如 果能,则输出所能搭建的双塔的最大高度,否则输出“Impossible” 。 【输入格式】 输入的第一行为一个数 N,表示水晶的数量。第二行为 N 个数,第 i 个数表示第 i 个水 晶的高度。 【输出格式】 输出仅包含一行,如果能搭成一座双塔,则输出双塔的最大高度,否则输出一个字符串 “Impossible” 。 【样例输入】 5 12435 【样例输出】 7 最基本的方法还是填鸭, 设 F[I,J,K]表示用前 I 个水晶组成一塔高度为 J 另一塔高度为 K 的可能性,则有状态转移方程:F[I,J,K] = F[I-1,J-AI,K] or F[I-1,J,K-AI] or F[I-1,J,K]。时间复 杂度为 O(N3H2) 。
第 30 页/共 50 页

信息学竞赛中的动态规划专题

实际上,如果设 F[I,J]表示用前 I 个水晶组成一对高度差为 J 的较低塔的最高高度,就 可以把时间复杂度降为 O(N2) 。 3.1.2 排序 排序是一件利器, 经常被使用在加入贪心思想的动态规划问题当中, 通过也会出现在避 免出现重复的问题当中, 贪心思想的例子前面说过了很多, 下面将举例说明排序在动态规划 问题中的应用。 GYoi 2007 购物计划 【题目描述】 宁宁利用假期打工赚了一大笔钱, 这使得她非常想上街进行一次大采购。 宁宁有个坏习 惯,看到东西就想买。 阿月为此伤透了脑筋, 最后他决定为宁宁来计划先买哪些东西后买哪些东西, 以此来为 宁宁省钱。宁宁也很心疼自己的钱,于是决定按照阿月的计划来安排买东西的先后顺序,但 是有一点可以肯定:只要她口袋里的钱数不低于 m 元就要继续买东西。 阿月需要你的帮助,他希望宁宁最后剩下的钱越多越好。 【输入格式】 输入第一行包括三个正整数 n,m 和 s(n≤100,0≤m,s≤10000) ,表示街上出售的商 品共有 n 种,而宁宁口袋里最初有 s 元钱。第二行包含 n 个用空格分隔的不超过 1000 的正 整数,表示对应商品的价格。 【输出格式】 输出只包含一个非负整数 t,即宁宁最后能剩下的最大钱数。 【样例输入】 4 5 10 2742 【样例输出】 4 【样例说明】 阿月要求宁宁先买商品 1 和商品 3 之后,宁宁只剩下 4 元钱,低于 m = 5 元,于是停止 购物,最后剩下 4 元。 宁宁停止购物有两种情况:钱数低于 m 元或者没有东西可买。第一种情况用填鸭的方 法可以轻松解决。 而第二种情况则需要提前判断, 如何判断买过一些东西之后什么都买不起 了呢?为了保证买不起 A[I]时,A[I+1..N]也都买不起,需要把商品的价值从小到大排序,从 小的开始买,累和为 t,满足 s-t<A[I]时,就什么也买不起了。 是否可能不是从小连续的购买方法也会导致什么也买不起了呢?假设这样是可以的, 那 么其肯定不是最优解(证明很简单) ,不必考虑。
第 31 页/共 50 页

信息学竞赛中的动态规划专题

Greater NewYork 2006 Margaritas on the River Walk http://poj.org/problem?id=3093 【题目描述】 有几种不同价格的玛格丽塔酒,给你一定的钱,让你去买酒。规定每种酒只能买一瓶, 而且要买到你没有足够的钱去买其它的酒为止。 问总共有多少种不同的购买方案。例如,你有 25 元钱,有六种酒,价格如下 Vendor A B C D H J Price 8 9 8 7 16 5 可 能 的 购 买 方 案 有 ABC(25), ABD(24), ABJ(22), ACD(23), ACJ(21), ADJ( 20), AH(24), BCD(24), BCJ(22), BDJ(21), BH(25), CDJ(20), CH(24), DH(23) HJ(21) 共 15 种方案。 【输入格式】 第一行包括两个正整数 N 和 V,表示酒的种类和持有的钱数,接下来一行包含 N 个正 整数表示每种酒的价格。 【输出格式】 方案总数。 【样例输入】 6 25 8 9 8 7 16 5 【样例输出】 15 题目要求剩下的钱数要小于任何未选择的酒的价格, 即小于未被选择的最小价格。 因此, 我们需要对所有酒按价格由小到大排序,再作讨论。 假设未被选择的最小价格的酒是第 I 个, 那么首先可以确定前 I-1 个酒一定是被选择的, 亦可以确定第 I+1 个到第 N 个酒的所有可行组合的价格和 S 满足 V - V[I] < S + Sum[I-1] <= V , 其中 Sum[I]为前 I 个酒的价格和。这样,枚举所有的 I 然后再找出满足条件的组合的个 数(还是利用填鸭)即是本题的答案。 Noip 2001 数的划分 http://122.139.62.222/problem.php?id=1539 【题目描述】 将整数 n 分成 k 份,且每份不能为空,任意两份不能相同(不考虑顺序)。 例如:n=7,k=3,下面三种分法被认为是相同的。 1,1,5; 1,5,1; 5,1,1; 问有多少种不同的分法。 【输入格式】
第 32 页/共 50 页

信息学竞赛中的动态规划专题

n,k (6<n≤200,2≤k≤6)。 【输出格式】 一个整数,即不同的分法。 【样例输入】 4 5 10 2742 【样例输出】 4 为了避免重复, 我们需要按照不下降的顺序进行排列。 我们形象地可以把 n 的 k 份自然 数划分看作 n 块积木堆成 k 列,那么不妨设这 n 块积木从左到右被堆成“阶梯状” 。比如, 下图表示的是 3 种 10 的 4 份自然数划分。

而将该图旋转 90 度,可以很容易想出一种状态表示方法。

设 F[I,J,K]表示把 J 划分成 I 份最大为 K 的划分方案数,则有 F[I,J,K] = ∑F[I-1,J-K,L], 其中 L = 1..K。时间复杂度为 O(N4) 。 而如果观察第一个图,我们还可以得到一种状态表示方式。设 F[I,J]表示把 I 划分成 J 份的划分方案数,则有 F[I,J] = ∑F[I-J,K] ,其中 K = 0..J。时间复杂度为 O(N3) 。 又由于 F[I,J]=∑F[I-J,K] (K = 0..J) =∑F[I-J,K] (K = 0..J-1) +F[I-J,J] = F[I-1,J-1]+F[I-J,J], 2 这样就把时间复杂度降为 O(N ) 。 3.1.3 预处理 预处理也是非常常见的动态规划辅助方法, 前面同样说过很多例子, 在这里再介绍一个
第 33 页/共 50 页

信息学竞赛中的动态规划专题

新问题——最大对角阵问题。 Oibh2005 创意吃鱼法 http://122.139.62.222/problem.php?id=1863 【问题描述】 回到家中的猫猫把三桶鱼全部转移到了她那长方形大池子中, 然后开始思考: 到底要以 何种方法吃鱼呢(猫猫就是这么可爱,吃鱼也要想好吃法 ^_*) 。她发现,把大池子视为 01 矩阵(0 表示对应位置无鱼,1 表示对应位置有鱼)有助于决定吃鱼策略。 在代表池子的 01 矩阵中,有很多的正方形子矩阵,如果某个正方形子矩阵的某条对角 线上都有鱼,且此正方形子矩阵的其他地方无鱼,猫猫就可以从这个正方形子矩阵“对角线 的一端”下口,只一吸,就能把对角线上的那一队鲜鱼吸入口中。 猫猫是个贪婪的家伙,所以她想一口吃掉尽量多的鱼。请你帮猫猫计算一下,她一口下 去,最多可以吃掉多少条鱼? 【输入格式】 第一行有两个整数 n 和 m(n,m≥1) ,描述池塘规模。接下来的 n 行,每行有 m 个数字 (非“0”即“1” ) 。每两个数字之间用空格隔开。 【输出格式】 只有一个整数——猫猫一口下去可以吃掉的鱼的数量,占一行,行末有回车。 【样例输入】 46 010100 001010 110001 011010 【样例输出】 3 我们所要求的是一个对角线为 1,其余地方都为 0 的子正方形,考虑到对角线实际上是 有左上到右下和从右上到左下这两种方向的,不失一般性,首先考虑左上到右下的方向。记 F[I,J]为子正方形的右下角坐标为(I,J)所能产生的最优对角线的长度, Left[I,J]为(I,J)的左边有 多少个连续的 0,Up(I,J)表示(I,J)的上边有多少个连续的 0,则有: (I,J)为 1 时,F[I,J] = Min {F[I-1,J-1],Up[I,J],Left[I,J]}+1 其中,Up[I,J]和 Left[I,J]需要预处理,可以在 O(N2)的时间内解决,动态规划的时间 复杂度也为 O(N2) ,故整个算法的时间复杂度为 O(N2) 。 如果动态规划的时间复杂度较高, 往往可以考虑通过提高预处理的时间复杂度来降低整 个算法的时间复杂度。 3.2.1 改进状态表示方法
第 34 页/共 50 页

信息学竞赛中的动态规划专题

状态的规模与状态表示的方法密切相关, 通过改进状态表示减小状态总数是应用较为普 遍的一种方法。 USACO 5.6.2 Raucous Rockers http://122.139.62.222/problem.php?id=1460 【问题描述】 现有 n 首由 Raucous Rockers 演唱组录制的珍贵的歌曲,计划从中选择一些歌曲来发行 m 张唱片,每张唱片至多包含 t 分钟的音乐,唱片中的歌曲不能重叠。按下面的标准进行选 择: (1)这组唱片中的歌曲必须按照它们创作的顺序排序; (2)包含歌曲的总数尽可能多。 【输入格式】 n,m,t, (1≤n, m, t≤20)和 n 首歌曲的长度,它们按照创作顺序排序,没有一首歌 超出一张唱片的长度,而且不可能将所有歌曲的放在唱片中。 【输出格式】 输出所能包含的最多的歌曲数目。 【样例输入】 452 4342 【样例输出】 3 设 N 首歌曲按照写作顺序排序后的长度为 L[1..N],F[I,J,K]表示前 I 首歌曲,用 J 张唱 片另加 K 分钟来录制,最多可以录制的歌曲数目,则有: K≥L[I]时 F[I,J,K]=Max{F[I-1,J,K-L[I]],F[I-1,J,K]} K<L[I]时 F[I,J,K]=Max{F[I-1,J-1,T-L[i]],F[I-1,J,K]} 该算法的时间复杂度为 O(NMT) 。当数据规模较大时无法满足要求,下面我们来考虑 通过改进状态表示提高算法的时间效率。 本题的最优目标是用给定长度的若干张唱片录制尽可能多的歌曲, 这实际上等价于在录制给 定数量的歌曲时尽可能少地使用唱片。所谓“尽可能少地使用唱片” ,就是指使用的完整的 唱片数尽可能少,或是在使用的完整的唱片数相同的情况下,另加的分钟数尽可能少。那么 设 G[I,J]=(A,B)表示在前 I 首歌曲中选取 J 首录制所需的最少唱片为: A 张唱片另加 B 分钟, 则有: G[I,J]=Min{G[I-1,J],G[I-1,J-1]+L[i]} 这样题目所求的最大值是: Max{K | G[N,K] ≤ (M-1,T)} 。该算法总的时间复杂度为 2 O(N )。
第 35 页/共 50 页

信息学竞赛中的动态规划专题

我们可以看到: 应用不同的状态表示方法设计出的动态规划算法迥然不同。 改进状态表 示可以减少状态总数,进而降低算法的时空复杂度,在动态规划的优化中占有重要的地位。 3.2.2 选择合适的动态规划方向 这里说的方向是在动态规划方法实现中的方向, 即正向或逆向。 而实际上正向或逆向的 动态规划都被我们熟知,那么这里介绍一下双向的动态规划。 Mid-Central European 1999 Dividing up http://acm.hit.edu.cn/hoj/problem/view?id=1141 【问题描述】 有价值分别为 1..6 的大理石各 A[1..6]块,现要将它们分成两部分,使得两部分价值和 相等,问是否可以实现。其中大理石的总数不超过 20000。 【输入格式】 6 个数字,表示 A[1..6]。 【输出格式】 “Can be divided.”或“Can't be divided.” 。 【样例输入】 101200 【样例输出】 Can't be divided. 首先令 S=∑(I*A[I]),若 S 为奇数,则不可能实现,否则令 Mid=S/2,则问题转化为能 否从给定的大理石中选取部分大理石,使其价值和为 Mid。 设 M[I,J]表示能价值为 1..I 的大理石中选出部分大理石,使其价值和为 J 的可能性,则有: M[I,J] = M[I-1,J] or M[I-1,J-I*K],时间复杂度为 O(N2Mid)。 在 I 较小时,由于可选取的大理石的价值品种单一,数量也较少,因此值为 true 的状态 也较少,但随着 I 的增大,大理石价值品种和数量的增多,值为 true 的状态也急剧增多,使 得规划过程的速度减慢,影响了算法的时间效率。 那么, 我们不妨从两个方向分别进行规划, 分别求出从价值为 1..3 的大理石中选出部分 大理石所能获得的所有价值和, 和从价值为 4..6 的大理石中选出部分大理石所能获得的所有 价值和。最后通过判断两者中是否存在和为 Mid 的价值和,由此,可以得出问题的解。 状态转移方程改进为: 当 I≤3 时 M[I,J]=M[I,J] or M[I-1,J-I*K] 当 I>3 时 M[I,J]=M[I,J] or M[I+1,J-I*K] 这样,若存在 K,使得 M[3,K]=true 且 M[4,Mid-K]=true,则可以实现题目要求,否则无 法实现。
第 36 页/共 50 页

信息学竞赛中的动态规划专题

上图基本反映了本题优化的效果。 可以得出结论: 双向扩展以减少状态量的方法不仅适 用于状态空间搜索,同样适用于动态规划。 3.2.3 减少每次状态转移的状态数 这里介绍一下四边形不等式及其应用,引例就用经典的石子合并问题。 Noi1995 石子合并问题 http://122.139.62.222/problem.php?id=1868 【题目描述】 在一个操场上摆放着一排 n(n≤20)堆石子。现要将石子有次序地合并成一堆。规定 每次只能选相邻的 2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。 试编程求出将 n 堆石子合并成一堆的最小得分和最大得分以及相应的合并方案。 这是一个典型的二维状态划分的动态规划,设 F[I,J]表示合并 D[I..J]所得到的最小得分 (最大得分同理) ,W[I,J]表示 D[I..J]区间的石子的总得分,则有 F[I,J] = Min{F[I,K-1] + F[K,J]}+W[I,J]。 当函数 G[I,J]满足 G[I,J] + G[I?,J?] ≤ G[I?,J] + G[I,J?]且 I≤I?≤J≤J?时,称 G 满足四边 形不等式。 在石子合并问题中, W 显然满足四边形不等式。 当函数 G[I,J]满足 G[I?,J]≤G[I,J?] 且 I≤I?≤J≤J?时称 G 关于区间包含关系单调,简称单调。那么在石子合并问题中,W 也显 然单调。由递推关系和数学归纳法可知,F 也满足四边形不等式。 令 S[I,J] = Max{K | F[I,J] = F[I,K-1]+F[K,J]+W[I,J] },即令 F[I,J]取得最小值的 K 的最大 值。可以证明 S 单调,即 I≤I?≤J≤J?时,S[I?,J]≤S[I,J?]。 由于证明过于复杂, 这里只证明要用的结论, 即 I≤J 且 I?=I,J?=J+1 时, S[I,J]≤S[I,J+1]。 由于 F 满足四边形不等式,则有:K≤K?≤J≤J+1 时,F[K,J]+F[K?,J+1]≤F[K?,J]+F[K,J+1], 设 FK[I,J]=F[I,K-1]+F[K,J]+W[I,J],不等式左右两边添加 4 项有: (F[I,K-1]+F[K,J]+W[I,J])+(F[I,K?-1]+F[K?,J+1]+W[I,J+1]) ≤ (F[I,K-1]+F[K,J+1]+W[I,J+1]) + (F[I,K?-1]+F[K?,J]+W[I,J]) 即 FK[I,J]+FK'[I,J+1]≤FK[I,J+1]+FK'[I,J]。 另一方面,要证明 S[I,J]≤S[I,J+1],只要证明对于所有 I<K≤K?≤J 且 FK?[I,J]≤FK[I,J] (由 S 定义得) ,有:FK?[I,J+1]≤FK[I,J+1]。加上面结论,得证。 同理可证 S[I,J+1]≤S[I+1,J+1]。则有:S[I,J]≤S[I,J+1]≤S[I+1,J+1]。
第 37 页/共 50 页

信息学竞赛中的动态规划专题

这样石子归并问题的时间复杂度就变为了:

? n ?1 n ? ? n ?1 ? ? O? ( 1 ? s [ i ? 1 , j ] ? s [ i , j ? 1 ]) ? O ? ? (n ? i ? s[i ? 1, n] ? s[1, n ? i]) ? ? O n 2 ?? ? ? ? i ?1 ? ? i ?1 j ?i ?1 ?

? ?

同样的方法也适用于前面提到过的 I-KeyBoard,设 F[I,J]表示前 I 个键盘存有前 J 个字 母的最小代价和,则有:F[I,J] = Min{F[I-1,K] + G[K + 1,J]},其中 G[K + 1,J]表示把第 K+1 个字母到第 J 个字母存在一个键上的最小代价和。G 单调且满足四边形不等式,则 F 也满足 四边形不等式,则用同样的方法可以把其时间复杂度降为 O(N2) 。对于利用四边形不等式 优化 I-KeyBoard 题目时需要注意的是:递推的时候要按照 I 递增,J 递减的顺序来进行。

第 38 页/共 50 页

信息学竞赛中的动态规划专题

4. 近年来 Noi 动态规划题目分析
Noi 作为每年一度的全国性的青少年信息学竞赛, 肩负着为中国信息学奥林匹克集训队 选拔优秀选手的任务,题目难度较大。其中动态规划也成为重点考察的算法对象之一,我们 接下来要讨论的就是近年来(2005 年以来)Noi(夏令营)中出现的动态规划题目。 Noi2005 瑰丽华尔兹 http://122.139.62.222/problem.php?id=1869 【题目描述】 你跳过华尔兹吗?当音乐响起,当你随着旋律滑动舞步,是不是有一种漫步仙境的惬 意? 众所周知,跳华尔兹时,最重要的是有好的音乐。但是很少有几个人知道,世界上最伟 大的钢琴家一生都漂泊在大海上,他的名字叫丹尼·布德曼·T.D.·柠檬·1900,朋友们都 叫他 1900。 1900 在 20 世纪的第一年出生在往返于欧美的邮轮弗吉尼亚号上。很不幸,他刚出生 就被抛弃,成了孤儿。1900 孤独的成长在弗吉尼亚号上,从未离开过这个摇晃的世界。也 许是对他命运的补偿,上帝派可爱的小天使艾米丽照顾他。 可能是天使的点化,1900 拥有不可思议的钢琴天赋:从未有人教,从没看过乐谱,但 他却能凭着自己的感觉弹出最沁人心脾的旋律。当 1900 的音乐获得邮轮上所有人的欢迎 时,他才 8 岁,而此时,他已经乘着海轮往返欧美大陆 50 余次了。 虽说是钢琴奇才,但 1900 还是个孩子,他有着和一般男孩一样的好奇和调皮,只不过 更多一层浪漫的色彩罢了: 这是一个风雨交加的夜晚, 海风卷起层层巨浪拍打着弗吉尼亚号, 邮轮随着巨浪剧烈的摇摆。船上的新萨克斯手迈克斯·托尼晕船了,1900 招呼托尼和他一 起坐到舞厅里的钢琴上,然后松开了固定钢琴的闸,于是,钢琴随着海轮的倾斜滑动起来。 准确的说,我们的主角 1900、钢琴、邮轮随着 1900 的旋律一起跳起了华尔兹,随着“嘣嚓 嚓”的节奏,托尼的晕船症也奇迹般的消失了。后来托尼在回忆录上这样写道:

大海摇晃着我们 使我们转来转去 快速的掠过灯和家具 我意识到我们正在和大海一起跳舞 真是完美而疯狂的舞者
晚上在金色的地板上快乐的跳着华尔兹是不是很惬意呢?也许, 我们忘记了一个人, 那 就是艾米丽,她可没闲着:她必须在适当的时候施展魔法帮助 1900,不让钢琴碰上舞厅里 的家具。 不妨认为舞厅是一个 N 行 M 列的矩阵,矩阵中的某些方格上堆放了一些家具,其他的 则是空地。钢琴可以在空地上滑动,但不能撞上家具或滑出舞厅,否则会损坏钢琴和家具, 引来难缠的船长。 每个时刻, 钢琴都会随着船体倾斜的方向向相邻的方格滑动一格, 相邻的方格可以是向 东、向西、向南或向北的。而艾米丽可以选择施魔法或不施魔法:如果不施魔法,则钢琴会 滑动;如果施魔法,则钢琴会原地不动。 艾米丽是个天使, 她知道每段时间的船体的倾斜情况。 她想使钢琴在舞厅里滑行的路程 尽量长,这样 1900 会非常高兴,同时也有利于治疗托尼的晕船。但艾米丽还太小,不会算,
第 39 页/共 50 页

信息学竞赛中的动态规划专题

所以希望你能帮助她。 【输入格式】 输入文件的第一行包含 5 个数 N, M, x, y 和 K。N 和 M 描述舞厅的大小,x 和 y 为钢琴 的初始位置; 我们对船体倾斜情况是按时间的区间来描述的, 且从 1 开始计算时间, 比如 “在 [1, 3]时间里向东倾斜,[4, 5]时间里向北倾斜” ,因此这里的 K 表示区间的数目。 以下 N 行,每行 M 个字符,描述舞厅里的家具。第 i 行第 j 列的字符若为‘ . ’ ,则 表示该位置是空地;若为‘ x ’ ,则表示有家具。 以下 K 行, 顺序描述 K 个时间区间, 格式为: si ti di(1 ≤ i ≤ K)。 表示在时间区间[si, ti]内,船体都是向 di 方向倾斜的。di 为 1, 2, 3, 4 中的一个,依次表示北、南、西、东(分 别对应矩阵中的上、下、左、右) 。输入保证区间是连续的,即 s1 = 1 ti = si-1 + 1 (1 < i ≤ K) tK = T 【输出格式】 输出文件仅有 1 行,包含一个整数,表示钢琴滑行的最长距离(即格子数) 。 【样例输入】 45413 ..xx. ..... ...x. ..... 134 451 672 【样例输出】 6 【样例说明】 钢琴的滑行路线:

钢琴在“×”位置上时天使使用一次魔法,因此滑动总长度为 6。 【评分方法】
第 40 页/共 50 页

信息学竞赛中的动态规划专题

本题没有部分分, 你的程序的输出只有和我们的答案完全一致才能获得满分, 否则不得 分。 【数据范围】 50%的数据中,1≤N, M≤200,T≤200; 100%的数据中,1≤N, M≤200,K≤200,T≤40000。 最基本的动态规划就是设 F[T,I,J]表示经过 T 个单位时间,在位置(X,Y)时的最大滑动距 离,则有 F[T,I,J] = Max (F[T,I,J], F[T-1,I-Dx,J-Dy] + 1),时间复杂度为 O(MNT) 。 数据规模很具有提示性,使我们考虑从每一段时间入手。设 F[I,J,K]表示在第 I 段时间 末在(J,K)处滑行的最长距离。则有: F[I,J,K] = Max{F[I-1,J0,K0],F[I-1,J1,K1]+1,F[I-1,J2,K2]+2,..,F[I-1,JN,KN]+N} 这样的时间复杂度仍然是 O(MNT) 。

以一个方向为例,在求 A 的时候,需要统计黄色框中的最大值,而求 B 的时候需要统 计绿色框中的最大值。 在求 A 的过程中统计红色框中的最大值, 设为 OP, 则在求 B 的时候, 只需要考虑 OP 和 C 处,大大减少了重复运算。如果绿色框中的最大值不在 B,那么 OP 可 以继续使用, 否则需要重新计算 OP。 因为要不时的重新计算 OP, 时间复杂度还是 O (MNT) , 但却比前面的方法快了很多,可以通过 80%的数据。如果我们用动态的 Heap 维护这些最大 值,可以把时间复杂度降到 O(MNKlogK) 。 事实上,在计算 F 的时候可以用单调队列,所谓的单调队列,就是维护一个这样的队 列: 每个点记录两个值 time-该点加入队列的时间(对于本题就是该点的位置) value-该点的权值 维护该队列中所有点的 time 和 value 均单调(对于本题 value 递减,time 递增) 。 该队列的操作有: 插入一个点 (T,V) :将队列尾 < V 的点删除,将该点加入队尾; 统计 T 时队列中的最大权:将队头 < T 的点删除,输出队头的点。 每个点加入和删除队列最多 1 次,这样就不需要重新计算 OP,动态规划的时间复杂度 就是 O(MNK)了。 Noi2005 聪聪和可可 http://122.139.62.222/problem.php?id=1870 【题目描述】 在一个魔法森林里, 住着一只聪明的小猫聪聪和一只可爱的小老鼠可可。 虽然灰姑娘非 常喜欢她们俩,但是,聪聪终究是一只猫,而可可终究是一只老鼠,同样不变的是,聪聪成 天想着要吃掉可可。 一天,聪聪意外得到了一台非常有用的机器,据说是叫 GPS,对可可能准确的定位。 有了这台机器,聪聪要吃可可就易如反掌了。于是,聪聪准备马上出发,去找可可。而可怜 的可可还不知道大难即将临头,仍在森林里无忧无虑的玩耍。小兔子乖乖听到这件事,马上
第 41 页/共 50 页

信息学竞赛中的动态规划专题

向灰姑娘报告。灰姑娘决定尽快阻止聪聪,拯救可可,可她不知道还有没有足够的时间。 整个森林可以认为是一个无向图,图中有 N 个美丽的景点,景点从 1 至 N 编号。小动 物们都只在景点休息、玩耍。在景点之间有一些路连接。 当聪聪得到 GPS 时,可可正在景点 M(M≤N)处。以后的每个时间单位,可可都会选择 去相邻的景点(可能有多个)中的一个或停留在原景点不动。而去这些地方所发生的概率是相 等的。假设有 P 个景点与景点 M 相邻,它们分别是景点 R、景点 S,??景点 Q,在时刻 T 可可处在景点 M,则在(T+1)时刻,可可有 1/(P +1)的可能在景点 R,有 1/(P +1)的可能在景 点 S,??,有 1/(P +1)的可能在景点 Q,还有 1/(P +1)的可能停在景点 M。 我们知道,聪聪是很聪明的,所以,当她在景点 C 时,她会选一个更靠近可可的景点, 如果这样的景点有多个,她会选一个标号最小的景点。由于聪聪太想吃掉可可了,如果走完 第一步以后仍然没吃到可可,她还可以在本段时间内再向可可走近一步。 在每个时间单位,假设聪聪先走,可可后走。在某一时刻,若聪聪和可可位于同一个景 点,则可怜的可可就被吃掉了。 灰姑娘想知道,平均情况下,聪聪几步就可能吃到可可。而你需要帮助灰姑娘尽快的找 到答案。 【输入格式】 数据的第 1 行为两个整数 N 和 E,以空格分隔,分别表示森林中的景点数和连接相邻 景点的路的条数。 第 2 行包含两个整数 C 和 M,以空格分隔,分别表示初始时聪聪和可可所在的景点的 编号。 接下来 E 行,每行两个整数,第 i+2 行的两个整数 Ai 和 Bi 表示景点 Ai 和景点 Bi 之 间有一条路。 所有的路都是无向的,即:如果能从 A 走到 B,就可以从 B 走到 A。输入保证任何两 个景点之间不会有多于一条路直接相连,且聪聪和可可之间必有路直接或间接的相连。 【输出格式】 输出 1 个实数, 四舍五入保留三位小数, 表示平均多少个时间单位后聪聪会把可可吃掉。 【样例输入 1】 43 14 12 23 34 【样例输出 1】 1.500 【样例说明 1】 开始时,聪聪和可可分别在景点 1 和景点 4。 第一个时刻,聪聪先走,她向更靠近可可(景点 4)的景点走动,走到景点 2,然后走到 景点 3;假定忽略走路所花时间。 可可后走,有两种可能:
第 42 页/共 50 页

信息学竞赛中的动态规划专题

第一种是走到景点 3,这样聪聪和可可到达同一个景点,可可被吃掉,步数为 1,概率 为 1/2。第二种是停在景点 4,不被吃掉。概率为 1/2。 到第二个时刻,聪聪向更靠近可可(景点 4)的景点走动,只需要走一步即和可可在同一 景点。因此这种情况下聪聪会在两步吃掉可可。 所以平均的步数是 1*1/2 + 2 * 1/2 = 1.5 步。 【样例输入 2】 99 93 12 23 34 45 36 46 47 78 89 【样例输出 2】 2.167 【样例说明 2】 森林如下图所示:

【数据范围】 对于 50%的数据,1≤N≤50; 对于所有的数据,1≤N,E≤1000。 这是近几年 Noi 中出现的最简单的一道题(没有之一) ,它的出现让很多有了原来 Noi 也可以 AC 的感想。 言归正传,题目的主要思想是动态规划(记忆化搜索) 。设 F[X,Y]表示可可在 X 点,聪 聪在 Y 点时 Gameover 的平均步数。 在已知可可位置时, 聪聪的移动方法是题目本身规定的。 不妨设 G[X,Y]表示可可在 X 点,聪聪在 Y 点时,聪聪下一步移动到的位置,而 T[X]表示与 X 相连的点的个数,S[X][I]表示与 X 相连的第 I 个点。
第 43 页/共 50 页

信息学竞赛中的动态规划专题

那么有状态转移方程 F[X,Y] = (∑F[S[X][K],G[X,Y]] + F[X,G[X,Y]]) /( T[x] + 1) + 1。 关键是对 G[X][Y]的初始化,用 Floyed 效率太低,大数据肯定超时。Heap+Dijkstra 可 以接受,复杂度为 O( (N+E)logN) 。 最好的方法就是 BFS。求权值为 1 的任两点间最短路的时间复杂度为 O(NE) 。动态规 2 划的时间复杂度为 O(N ) 。整个算法的时间复杂度为 O(NE) 。 Noi2006 网络收费 http://122.139.62.222/problem.php?id=1871 【题目描述】 网络已经成为当今世界不可或缺的一部分。每天都有数以亿计的人使用网络进行学习、 科研、娱乐等活动。然而,不可忽视的一点就是网络本身有着庞大的运行费用。所以,向使 用网络的人进行适当的收费是必须的,也是合理的。 MY 市 NS 中学就有着这样一个教育网络。 网络中的用户一共有 2N 个, 编号依次为 1, 2, 3, ?, 2N。这些用户之间是用路由点和网线组成的。用户、路由点与网线共同构成一个满二 叉树结构。树中的每一个叶子结点都是一个用户,每一个非叶子结点(灰色)都是一个路由 点,而每一条边都是一条网线(见下图,用户结点中的数字为其编号) 。

1

2

3

4

5

6

7

8

MY 网络公司的网络收费方式比较奇特,称为“配对收费” 。即对于每两个用户 i, j (1 ≤i < j ≤2N ) 进行收费。由于用户可以自行选择两种付费方式 A、B 中的一种,所以网络 公司向学校收取的费用与每一位用户的付费方式有关。 该费用等于每两位不同用户配对产生 费用之和。 为了描述方便,首先定义这棵网络树上的一些概念: 祖先: 根结点没有祖先,非根结点的祖先包括它的父亲以及它的父亲的祖先; 管辖叶结点: 叶结点本身不管辖任何叶结点, 非叶结点管辖它的左儿子所管辖的叶结点与它的右儿子 所管辖的叶结点; 距离: 在树上连接两个点之间的用边最少的路径所含的边数。

第 44 页/共 50 页

信息学竞赛中的动态规划专题

对于任两个用户 i, j (1≤i<j≤2N ),首先在树上找到与它们距离最近的公共祖先:路 由点 P,然后观察 P 所管辖的叶结点(即用户)中选择付费方式 A 与 B 的人数,分别记为 nA 与 nB,接着按照网络管理条例第 X 章第 Y 条第 Z 款进行收费(如下表) ,其中 Fi, j 为 i 和 j 之间的流量,且为已知量。 i 付费方式 A A B B A A B B j 付费方式 A B A B A B A B nA≥nB nA<nB nA 与 nB 大小关系 付费系数 k 2 1 1 0 0 1 1 2 k * Fi, j 实际付费

由于最终所付费用与付费方式有关, 所以 NS 中学的用户希望能够自行改变自己的付费 方式以减少总付费。 然而, 由于网络公司已经将每个用户注册时所选择的付费方式记录在案, 所以对于用户 i,如果他/她想改变付费方式(由 A 改为 B 或由 B 改为 A) ,就必须支付 Ci 元给网络公司以修改档案(修改付费方式记录) 。 现在的问题是,给定每个用户注册时所选择的付费方式以及 Ci,试求这些用户应该如 何选择自己的付费方式以使得 NS 中学支付给网络公司的总费用最少(更改付费方式费用+ 配对收费的费用) 。 【输入格式】 输入文件中第一行有一个正整数 N。 第二行有 2N 个整数,依次表示 1 号,2 号,?,2N 号用户注册时的付费方式,每一个 数字若为 0,则表示对应用户的初始付费方式为 A,否则该数字为 1,表示付费方式为 B。 第三行有 2N 个整数,表示每一个用户修改付费方式需要支付的费用,依次为 C1, C2, …,CM 。( M=2N ) 以下 2N-1 行描述给定的两两用户之间的流量表 F,总第(i + 3)行第 j 列的整数为 Fi, j+i 。 (1≤i<2N,1≤j≤2N ? i) 所有变量的含义可以参见题目描述。 【输出格式】 你的程序只需要向输出文件输出一个整数, 表示 NS 中学支付给网络公司的最小总费用。 (单位:元) 【样例输入】 2 1010 2 2 10 9 10 1 2 21 3
第 45 页/共 50 页

信息学竞赛中的动态规划专题

【样例输出】 8 【样例说明】 将 1 号用户的付费方式由 B 改为 A,NS 中学支付给网络公司的费用达到最小。 【评分方法】 本题没有部分分, 你的程序的输出只有和我们的答案完全一致才能获得满分, 否则不得 分。 【数据规模和约定】 40%的数据中 N≤4; 80%的数据中 N≤7; 100%的数据中 N≤10,0≤Fi, j≤500,0≤Ci≤500 000 把配对收费规则转化一下,对于任两个用户 I,J,设它们的最近公共祖先(LCA)是 P。 如果在 P 上 na<nb,则 I,J 中谁是 A 谁支付 F[I,J]的费用,如果在 P 上 na≥nb,则 I,J 中谁是 B 谁支付 F[I,J]的费用,这样的转化让点对交费转移到单点交费,便可以开始进行树型动态 规划。 考虑到两种状态的具体选择情况和花费有直接的联系, 需要存在两种状态的具体选择情 况,于是要采用压缩状态的树型动态规划。设 F[I,J,S]表示在点 I 所管辖的所有用户中,有 J 个用户为 A,且在 I 的每个祖先 U 上的状态为 S 情况下的最少花费。则有状态转移方程: F[I,J,S] = F[Left,K,S+Ds]+F[Right,J-K,S+Ds]; Left 以及 Right 分别为 I 的左右儿子结点,Ds 为 S 的状态改变量。 复杂度分析:设 M=2N 粗略看来,空间复杂度是 O(M3),时间复杂度是 O(M4),对于本 题的数据可以同时 MLE 和 TLE 了。 把根节点看做第 0 层,叶节点就是第 N 层,对于任意的第 I 层,A 用户的个数最多只有 N-I 2 ,而祖先结点只有 I 个,即 S 最大只有 2I,相当于把 F[I,J,S]的后两维合并成一维,空间 复杂度其实只有 O(M2)。 再看时间复杂度,对于第 I 层,有 2I 个节点,每个节点的状态数是 O(M)的,状态转移 的复杂度是 O(2N-I),所以每层的复杂度是 O(M2)。总共有 n 层,所以状态转移的时间复杂度 是 O(M2N)。其它条件都进行预处理,整个算法的时间复杂度就化为了 O(M2N)。 Noi2006 千年虫 http://122.139.62.222/problem.php?id=1872 【问题描述】 千年虫是远古时代的生物,时隔几千万年,千年虫早已从地球上销声匿迹,人们对其知 之甚少。考古生物学家最近开始对其有了兴趣,因为一批珍贵的千年啊虫化石被发现,这些 化石保留了千年虫近乎完整的形态。 理论科学家们根据这些化石归纳出了千年虫的一般形态特征模型, 并且据此判定出千年 虫就是蜈蚣的祖先!但科学家 J 发现了实际与理论的一些出入,他仔细的研究了上百个千年 虫化石,发现其中大部分千年虫的形态都不完全符合理论模型,这到底是什么因素造成的 呢?理论科学家 K 敏锐的指出,千年虫的形态保存在化石中很有可能发生各种变化,即便
第 46 页/共 50 页

信息学竞赛中的动态规划专题

最细微的变化也能导致它不符合模型。 于是, 摆在科学家面前的新问题诞生了: 判断一个化石中的千年虫与理论模型的差距有 多大?具体来说,就是根据一个千年虫化石的形态 A,找到一个符合理论模型的形态 B,使 得 B 是最有可能在形成化石时变成形态 A。

1 2 3 4

1 2 3 4 5 5 6 7 8 9 7 8 9 10 11 6

头 躯干





理论学家提出的“千年虫形态特征模型”如下(如上图所示) :躯体由头、尾、躯干、足 四大部分构成。 1.头,尾用一对平行线段表示。称平行于头、尾的方向为 x 方向;垂直于 x 的方向为 y 方向; 2.在头尾之间有两条互不相交的折线段相连,他们与头、尾两条线段一起围成的区域称 为躯干,两条折线段都满足以下条件:拐角均为钝角或者平角,且包含奇数条线段,从 上往下数的奇数条垂直于 x 方向。 3.每条折线段从上往下数的第偶数条线段的躯干的另一侧长出一条足,即一个上、下底 平行于 x 方向的梯形或矩形,且其中远离躯干一侧的边垂直于 x 方向。 注意:足不能退化成三角形(即底边的长度均大于零) ,躯干两侧足的数目可以不一样。 (如上图,左边有 4 条足,右边有 5 条足) 可见,x-y 直角坐标系内,躯干和所有足组成的实心区 域的边界均平行或垂直于坐标轴。为了方便,我们假设所有 4,4 这些边界的长度均为正整数。 因此可以认为每个千年虫的躯 2,5 体都由一些单位方格拼成。每个单位方格都由坐标(x,y)唯一 3,5 1,3 确定。设头尾之间的距离为 n,则我们可以用 2× n 个整数来 2,5 描述一条千年虫 B(如右图) :将 B 沿平行 x 轴方向剖分成 1,4 n 条宽度为 1 的横条, 每个横条最左边一格的 x 坐标设为 Li, 3,4 最右一格的的 x 坐标设为 Ri。则(n,L1,L2,..,Ln,R1,R2,..Rn) 就确定了一条千年虫。 由于岁月的侵蚀,在实际发现的化石中,千年虫的形状并不满足上面理论模型的规则, 一些格子中的躯体已经被某些矿物质溶解腐蚀了。 地质、物理、生物学家共同研究得出: 1、腐蚀是以格子为单位的,只能一整格被腐蚀; 2、腐蚀是分步进行的,每一步只有一格被腐蚀;
1 2 3 4 5 L,R 第 47 页/共 50 页

信息学竞赛中的动态规划专题

3、如果去掉一个格子后躯体不连通了,那么这个格子当前不会被腐蚀; 4、 如果一个格子的左边邻格和右边邻格都还没被腐蚀, 那么这个格子当前不会被腐蚀; 5、与头相邻的格子不能全部被腐蚀,与尾相邻的格子不能全部被腐蚀; 倘若满足上面五条,我们仍然可以用(n,L?1,L?2,..,L?n,R?1,R?2,..R?n)来描述一个化石里头 的千年虫的形态。其中 L?i≤R?i。 例如下图:
1 2 3 4 5 L,R 3,4 3,4 3,5 1,3 2,3 1,4 3,3 腐蚀后 1 2 3 4 5 L?,R? 4,4 3,4 3,5 1,3 2,2 2,4 3,3

现在你的任务是, 输入一个化石里的千年虫的描述 A<n,L?,R?>,找一个满足理论模型的 千年虫的描述 B<n,L,R>, 使得 B 可以通过腐蚀过程得以变为 A, 且由 B 转化为 A 的代价(须 被腐蚀的格子数)最少。输出此最小代价。 【输入格式】 第一行为一个整数 n; 以下 n 行,每行两个整数,其中第 i 行为两个整数 L?i,R?i,用一个空格分开; 保证输入数据合法。 【输出格式】 仅一行,为一个整数,表示最少代价。 【输入样例】 7 44 34 35 13 22 24 33 【输出样例】 3 【样例说明】 如下图。
第 48 页/共 50 页

信息学竞赛中的动态规划专题

1

2

3

4

5

【数据规模和约定】 30%的数据 n≤100, 50%的数据 n≤1000, 70%的数据 n≤100000, 100%的数据 n≤1000000,

0≤L?i≤R?i≤100 0≤L?i≤R?i≤1000 0≤L?i≤R?i≤1000 0≤L?i≤R?i≤1000000

【评分方法】 本题没有部分分, 你的程序的输出只有和我们的答案完全一致才能获得满分, 否则不得 分。 以一边为例,则千年虫的外形是一个类似梳子的样子,就是一段高,一段低。而我们要 做的,就是添加尽量少的方块,使得外形满足上诉的样子。设 F[I,J]表示搞定了前 I 行后第 I 行处于凹的一段且第 I 行的最终高度是 J 的状态下最小添加的方块数,G[I,J]表示搞定了前 I 行后第 I 行处于凸的一段且第 I 行的最终高度是 J 的状态下最小添加的方块数,设 V[I,J,K] 表示把第 I 行到第 J 行的部分都填到高度为 K 所需要的方块数,可以用 O(NL)初始化出来。 则有: F[I,J] = Min{G[K,H]} + V[K,I,J] G[I,J] = Min{F[K,H]} + V[K,I,J] 时间复杂度为 O(N2L2)。调整一下状态的安排方式则有: F[I,J] = Min{F[I-1,J], G[I-1,K]} + (J - H[I]) ,K<J G[I,J] = Min{G[I-1,J], F[I-1,K]} + (J - H[I]) , K>J 其中 H[I]是第 I 行的原始高度,时间复杂度为 O(NL2)。观察数据范围可知,即使把时 间复杂度降那 O(NL)也难逃 TLE 的魔爪(据说可以降下去,我没想出来) 。 我们需要在其中加入贪心要素,这里先讨论一种贪心准则:对于每一列,我们增加若干 方格,目标是使得这一列跟附近的几列一样高或者与比附近的几列高/低一些。如果是比附 近的几列高一些,我们不希望高太多(否则花费过高) 。 设 AI 为第 I 列的初始高度,,BI 为第 I 列增加若干方格后的高度(最终高度) ,我们猜 想:对于任意一列 I,存在 I 附近的一列 J 满足|J-I|≤C,使得|BI-AJ|≤D,其中 C,D 为常数。 取 C = N,D = 3 时,可以证明结论成立(奇怪,为什么取 C = N, D = 3? 另外证明也没有 什么技术含量,用反证法枚举所有情况,在此略去) 。 由于状态数为 7N 个,所以我们可以在 O(N)时间内解决本题。

第 49 页/共 50 页

信息学竞赛中的动态规划专题

参考书籍与相关材料 《树型动态规划的实例分析》 《动态规划中的提纯》 《贪婪的动态规划》 《动态规划算法的优化技巧》 《算法艺术与信息学竞赛》 《Noi2006 题目讨论——千年虫》 李彦亭 陈启峰 黄劲松 毛子青 刘汝佳 Noi 官方

第 50 页/共 50 页


相关文章:
动态规划习题集全
动态规划习题集全_理学_高等教育_教育专区。动态规划专题训练 护卫队【问题描述】 护卫车队在一条单行的街道前排成一队,前面河上是一座单行的桥。因为街道是一条...
动态规划习题答案
动态规划习题答案_工学_高等教育_教育专区。由复旦大学出版社出版,傅家良主编的运筹学方法与模型第八章动态规划习题答案2.某公司有资金 4 百万元向 A,B 和 C3 ...
动态规划习题
动态规划习题_理学_高等教育_教育专区。数学模型 第七章 动态规划 规划问题的...都可以用非线性规划 (特殊的可以用线性规划)模型来描述;因此,从原则上讲,一般...
经典的动态规划入门练习题
经典的动态规划入门练习题_工学_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 经典的动态规划入门练习题_工学_高等教育_教育专区。动态规划入门练习题 ...
动态规划练习题
动态规划练习题_语文_初中教育_教育专区。动态规划练习题 1. 设某工厂自国外进口一部精密仪器, 由机器制造厂至出口 港有三个港口可供选择,而进口港又有三个可...
动态规划习题
45页 20财富值 动态规划题目 38页 2财富值 动态规划_各种类型题 102页 10财富值 动态规划题 9页 免费如要投诉或提出意见建议,请到百度文库投诉中心反馈。 ...
动态规划练习题及解答1
动态规划练习题 [题 1] 多米诺骨牌(DOMINO) 问题描述:有一种多米诺骨牌是平面...习题答案选04_动态规划 2页 免费 动态规划习题精讲 暂无评价 51页 1下载券...
动态规划习题解题报告1
动态规划练习题及解答1 9页 2财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 动态规划习题解题报告1 我做百度文库...
动态规划和层次分析练习题
动态规划、层次分析作业汪帆 2011306200513 土规 1202 班第一题(动态规划练习) :为保证某一设备的正常运转,需备有三种不同的零件 E1 , E2 , E3 。若增加备用...
【Pascal-C++】资源类动态规划练习题
【Pascal-C++】资源类动态规划练习题_计算机软件及应用_IT/计算机_专业资料。【Pascal-C++】资源类动态规划练习题 1,采药 (medic.pas/c/cpp) 【问题描述】 辰辰...
更多相关标签: