《45道动态规划题目分析》由会员分享，可在线阅读，更多相关《45道动态规划题目分析（102页珍藏版）》请在金锄头文库上搜索。
1、算法艺术与信息学竞赛45道动态规划题目,刘汝佳,索引,【POJ1141】括号序列【POJ1191】棋盘分割【SPOJ196】决斗【AOA】跳舞机【AOA】积木游戏【AOA】艺术馆的火灾【AOA】机器人的名字【UVa10559】方块消除,索引,【AOA】公路巡逻【POJ1074】并行期望值【AOA】高性能计算机【AOA】模板匹配【AOA】不可解码的编码【AOA】青蛙的烦恼【AOA】排列问题【AOA】最优排序二叉树,索引,【POJ1038】 Bugs公司【UVa10531】迷宫统计【AOA】贪吃的九头龙【AOA】快乐的蜜月【AOA】移动机器人【UVa10271】佳佳的筷子【AOA】偷懒的工人【AO
2、A】铁路调度,索引,【POJ1691】平板涂色【POJ1947】道路重建【ZJUxxx】圆和多边形【AOA】铁球落地【UVA10118】免费糖果【AOA】丢三落四的老鼠【AOA】最长公共子序列问题【UVA10635】排列的LCS问题,索引,【UVAxxx】最长上升子序列问题【UVAxxx】最优二分检索树问题【POJ1180】任务调度问题【AOA】序列分割问题【AOA】多排列的LCS【POJ1159】回文词【AOA】友好城市【POJ1160】邮局,索引,【AOA】基因串【POJ1946】奶牛转圈【AOA】元件折叠【AOA】 DNA序列【AOA】最优布车方案,括号序列,定义如下规则序列（字符串）：
3、空序列是规则序列；如果S是规则序列，那么（S）和S也是规则序列；如果A和B都是规则序列，那么AB也是规则序列。例如，下面的字符串都是规则序列：()， ， ()， ()， ()， ()()这几个则不是规则序列：(， ， ， )(， ()现在，给出一些由(，)，构成的序列，请添加尽量少的括号，得到一个规则序列。,分析,di,j: 子串ij最少需要添加的括号数状态转移S形如(S)或者S: di+1,j-1S形如(S或者S: di+1,j+1S形如S)或者S: di,j-1+1长度大于1: di,k+dk+1,j (i=k=j-1)状态O(n2), 转移O(n), 共(n3),棋盘分割,将一个88的棋
4、盘进行如图所示的分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有n（n15）块矩形棋盘（每次切割都只能沿着棋盘格子的边进行）。,棋盘分割,原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘，并使各矩形棋盘总分的均方差最小。,分析,变形均方差公式平均值是一定的（等于所有方格里的数的和除以n）只需要让每个矩形总分的平方和尽量小,分析,考虑左上角坐标为(x1,y1)，右下角坐标为(x2,y2)的棋盘，设它把切割k次以后得到的k+1块矩形的总分平方和最小值为dk,
5、x1,y1,x2,y2状态转移: 沿着某横线切或者竖线切，然后选一块继续切, 如横着切的两类决策是dk-1,x1,y1,a,y2+sa+1,y1,x2,y2dk-1,a+1,y1,x2,y2+sx1,y1,a,y2 其中x1=a=x2,分析,状态dk,x1,y1,x2,y2设m为棋盘边长，则状态数目为m4n，决策数目为O(m)转移时间取决于计算sx1,y1,x2,y2的时间预处理先用O(m2)时间算出左上角为(1,1)的所有矩阵元素和，这样状态转移时间就是O(1)，总的时间复杂度为O(m5n),决斗,编号为1n的n个人按逆时针方向排成一圈，他们要决斗n-1场。每场比赛在某相邻两人间进行，败者退
6、出圈子，紧靠败者右边的人成为与胜者直接相邻的人。任意两人之间决斗的胜负都将在一矩阵中给出（如果Ai,j=1则i与j决斗i总是赢，如果Ai,j=0则i与j决斗时i总是输），求出所有可能赢得整场决斗的人的序号,分析,di,j表示是否有可能i和j相遇, 则第i个人能取得最后的胜利当且仅当di,i为true状态转移: 考虑相遇前的最后一步, 则dI,j为true当且仅当能找到一个k, 使得i能遇k, k能遇到j, 且i或者j能打败k状态有O(n2)个, 转移有O(n)个, 共O(n3),跳舞机,DDR的主要内容是用脚来踩踏板。踏板有4个方向的箭头，用1，2，3，4来代表每首歌曲有一个箭头序列，游戏者必
7、须按照这个序列依次用某一只脚踩相应的踏板。在任何时候，两只脚都不能在同一个踏板上，但可以同时待在中心位置0。,跳舞机,每一个时刻，必须移动而且只能移动一只脚去踩相应的箭头，另一只脚不许移动。跳DDR会消耗体力。从中心移动到任何一个箭头耗费2单位体力，从任何一个箭头移动到相邻箭头耗费3单位体力，移动到相对的箭头（1和3相对，2和4相对）耗费4单位体力，而留在原地再踩一下只需要1单位。给定一首舞曲, 每个箭头应该用哪只脚踩才能使体力消耗最少呢？例如对于序列LLUR, 用LLRR脚去踩，总的体力耗费为2 + 1 + 2 + 3 = 8单位,分析,目前左脚在位置x, 右脚在位置y, 从第k个箭头开始跳
8、, 最少体力耗费为dx,y,k, 则用左脚, dak, y, k+1 + effort(x, ak)用右脚, dx, ak, k+1 + effort(y, ak)状态是O(n)的，决策是O(1)的, 总时间复杂度为O(n),积木游戏,有N块编号依次为1，2，N的长方体积木。每块积木有三条不同边分别称为a、b、c边从积木中选出若干块分成M堆, 每堆至少有1块积木，并且第K堆中任意一块积木的编号要大于第K+1堆中任意一块积木的编号,积木游戏,每一堆积木要垂直摞成一根柱子,并满足除最顶上的一块积木外，任意一块积木的上表面同且仅同另一块积木的下表面接触，并且要求下面积木的上表面能包含上面的积木的下表
9、面，也就是说，要求下面积木的上表面两对边的长度分别大于等于上面积木两对边的长度。对于任意两块上下表面相接触的积木，下面积木的编号要小于上面积木的编号要求每堆积木的高度和尽量大,分析,我们从最后一堆积木开始, 一个个积木考虑记di,a,b,k为已经用了前a个积木得到了i根柱子, 目前顶面为积木b的第k个面, 以后还能获得的最大高度, 有三类决策新起一堆, di+1,a+1,a+1,k, 当im时合法加在当前堆, di,a+1,a+1,k, 当放得上时合法丢弃当前块, di,a+1,b,k, 随时合法状态O(n2m)个, 决策O(1), 总时间O(n2m),艺术馆的火灾,艺术馆着火了. 这是一幢两
10、层的小楼，每层有N个房间，用两个数分别表示艺术品价值和火势. 灭火器最多只能发射K次，每次发射将覆盖一个矩形的区域（矩形的高度可以是1也可以是2），所到之处不但火焰会被扑灭，艺术品也被摧毁。你需要决定灭火器每次应该怎样发射，才能将这次火灾的损失降到最低限度。损失等于摧毁的艺术品总价值加上剩余的火势总值,分析,模型：在一个2N的矩阵中，找出K个子矩阵。矩阵的每个元素有两个值V和F。题目要让K个子矩阵的V值和其他矩阵的F值之和最小，而如果我们令W=V-F，则目标转换为让K个子矩阵元素的W值之和最小 矩阵可以重叠，这给解题带来不便。我们可以不考虑重叠情况，如图所示,分析,用区域(i,j)来表示“第一
11、行第i个格子右边所有元素加上第二行第j个格子右边的所有元素”这个区域，用ds,i,j来表示在这个区域中选择s个子矩阵，它们的元素总和的最小值状态转移的决策是新矩形的放置, 有三类第一行第i个格子不用, ds,i+1,j在第一行从第i个格子开始放矩形, 设长度为L, 转移到ds-1,i+L,ji=j时还可放置宽度为2的矩形, 转移到ds-1, i+L, j+L状态O(kn2)个, 决策O(n), 转移时间O(1)(先预处理), 总时间O(kn3),机器人的名字,考虑一种基于重复子串的压缩方法用Stk表示k个相同的子串St(其中St称为重复子串，k是一个单字节整数，只占一个字符位置)如果这k个子串
12、并没有连在一起，则可以在Stk的后面加上S1t1S2 t2Sr tr（1tik，titi+1），表示在第ti个St的后面放置Si，Si称为插入子串St和Si也都可以是压缩后的字符串比如I_am_WhatWhat_is_WhatWhat的压缩结果为I_am_What4_is_2，长度为19 (例子中的空格用下划线“_”表示，数字2和4实际上是用单字节二进制表示的)名字不会以空格开始或结尾，大小写敏感,分析,令da,b表示以a, b为起止位置的串(记为Sa,b)的最短压缩长度, 则目标为d1,L状态转移连接: da,b = minda,i + di+1,b, a=ib压缩: 需要确定重复子串. 当
13、重复子串很多时, 决策枚举的代价较大压缩决策可以通过动态规划来枚举!,分析,ga,b,c表示将串Sa,b, 选择长度为c的重复子串进行压缩得到的最短长度. 枚举插入串(可能为空)的下一个位置i, 状态转移方程为,分析,边界条件da,b的状态转移方程如何较快的判断是否有Sa, a+c-1=Si, i+c-1? 从c=1开始递推, 总O(L3),分析,时间: 预处理O(L3), 核心O(L4), 共O(L4)空间g: 本来是三维的O(L3)的, 但注意到在每个式子里b参量没有发生变化, 故以b为阶段递推, 只需要O(L2)的空间预处理结果: 如果用ha,b,c表示是否有Sa, a+c-1=Sb,
14、b+c-1, 则又是三维的. 可以用链式存储, 用nexta,b表示子串Sa,b的下一个相同子串的开始位置, 则只需要O(L2)的空间,方块消除,n个带颜色方格排成一列，相同颜色的方块连成一个区域（如果两个相邻方块颜色相同，则这两个方块属于同一区域）游戏时，你可以任选一个区域消去。设这个区域包含的方块数为x，则将得到x2分方块消去之后将产生空列, 此时其右边的所有方块就会向左移, 直到所有方格连在一起,方块消除,下面是一个游戏的例子,分析,输入表示成两个长度为L的数组color和lenL表示有多少“段”不同的颜色方块colori表示第i段的颜色leni表示第i段的方块长度题目的例子成color
15、=1,2,3,1, len=1,4,3,1用(i,j,k)表示在第ij段方块的右边添加k个颜色为colorj的方块后得到的方块序列, 相当于考虑第ij段, 但让lenj的值增加k,分析,d i,j,k表示把序列(i,j,k)消除的最大得分考虑最后一段，有两类决策如果马上消掉，就是di,j-1,0+(lenj+k)2；如果和前面的若干段一起消，设这“若干段”中最后面的那一段是p(i=pj)，得分为di,p,k+lenj+dp+1,j-1,0, 其中colorp=colorj边界条件是f i,i-1,0=0时间O(n4), 建议用记忆化递归实现,公路巡逻,在一条没有分岔的公路上有n（n50）个关口，相邻两关口之间的距离是10km。所有车辆在公路上的最低速度为60km/h，最高速度为120km/h，且只能在关口处改变速度。有m(m300)辆巡逻车分别在时刻Ti从第ni个关口出发，匀速行驶到达第ni+1个关口，路上耗费时间为ti(s)。两辆车相遇指他们之间发生超车现象或同时到达某个关口。求一辆于6点整从第1个关口出发去第n个关口的车最少会与多少辆巡逻车相遇，以及在此情况下到达第n个关口的最早时刻。所有车辆到达关口的时刻必须是整秒。,
