算法艺术与信息学竞赛配套课件-动态规划.ppt

《算法艺术与信息学竞赛配套课件-动态规划.ppt》由会员分享，可在线阅读，更多相关《算法艺术与信息学竞赛配套课件-动态规划.ppt（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】偷懒的工人【AOA】铁路调度索引

2、【POJ1691】平板涂色【POJ1947】道路重建【ZJUxxx】圆和多边形【AOA】铁球落地【UVA10118】免费糖果【AOA】丢三落四的老鼠【AOA】最长公共子序列问题【UVA10635】排列的LCS问题索引【UVAxxx】最长上升子序列问题【UVAxxx】最优二分检索树问题【POJ1180】任务调度问题【AOA】序列分割问题【AOA】多排列的LCS【POJ1159】回文词【AOA】友好城市【POJ1160】邮局索引【AOA】基因串【POJ1946】奶牛转圈【AOA】元件折叠【AOA】DNA序列【AOA】最优布车方案括号序列定义如下规则序列（字符串）：空序列是规则序列；如果S是规则序列

3、，那么（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,x1,y1,x2,y2状态转移:沿着某某横线切或者竖线切，然后选一块选一块继续切,如横着

5、切的两类决策是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来代表每首歌曲有一个箭头序列，游戏者必须按照这个序列依次用某一只脚踩相应的踏板。在任何时候，两只脚都不能在同一个踏板上，但可以同时待在中心位置0。跳

7、舞机每一个时刻，必须移动而且只能移动一只脚去踩相应的箭头，另一只脚不许移动。跳DDR会消耗体力。从中心移动到任何一个箭头耗费2单位体力，从任何一个箭头移动到相邻箭头耗费3单位体力，移动到相对的箭头（1和3相对，2和4相对）耗费4单位体力，而留在原地再踩一下只需要1单位。给定一首舞曲,每个箭头应该用哪只脚踩才能使体力消耗最少呢？例如对于序列LLUR,用LLRR脚去踩，总的体力耗费为2+1+2+3=8单位分析目前左脚在位置x,右脚在位置y,从第k个箭头开始跳,最少体力耗费为dx,y,k,则用左脚,dak,y,k+1+effort(x,ak)用右脚,dx,ak,k+1+effort(y,ak)状态是

8、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)艺术馆的火灾艺术馆着火了.这是一幢两层的小楼，每层有N个房间，用两个数分别表示艺术品价值和火势.灭火器最多只能发射K次，每次发射将覆盖一个矩形的区域（矩形的高度可以是1也可以是2），所到之处不但火焰会被扑灭，艺术品也被摧毁。你需要决定灭火器每次应该怎

10、样发射，才能将这次火灾的损失降到最低限度。损失等于摧毁的艺术品总价值加上剩余的火势总值分析模型：在一个2N的矩阵中，找出K个子矩阵。矩阵的每个元素有两个值V和F。题目要让K个子矩阵的V值和其他矩阵的F值之和最小，而如果我们令W=V-F，则目标转换为让K个子矩阵元素的W值之和最小 矩阵可以重叠，这给解题带来不便。我们可以不考虑重叠情况，如图所示分析用区域(i,j)来表示“第一行第i个格子右边所有元素加上第二行第j个格子右边的所有元素”这个区域，用ds,i,j来表示在这个区域中选择s个子矩阵，它们的元素总和的最小值状态转移的决策是新矩形的放置,有三类第一行第i个格子不用,ds,i+1,j在第一行从

11、第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个子串并没有连在一起，则可以在Stk的后面加上S1t1S2 t2Sr tr（1tik，titi+1），表示在第ti个St的后面放置Si，Si称为插入子串St和Si也都可以是压缩后的字符串比如I_am_WhatWhat_is_WhatWhat的压缩结果为I

12、_am_What4_is_2，长度为19(例子中的空格用下划线“_”表示，数字2和4实际上是用单字节二进制表示的)名字不会以空格开始或结尾，大小写敏感分析令da,b表示以a,b为起止位置的串(记为Sa,b)的最短压缩长度,则目标为d1,L状态转移连接:da,b=minda,i+di+1,b,a=ib压缩:需要确定重复子串.当重复子串很多时,决策枚举的代价较大压缩决策可以通过动态规划来枚举!分析ga,b,c表示将串Sa,b,选择长度为c的重复子串进行压缩得到的最短长度.枚举插入串(可能为空)的下一个位置i,状态转移方程为分析边界条件da,b的状态转移方程如何较快的判断是否有Sa,a+c-1=Si

13、,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,b+c-1,则又是三维的.可以用链式存储,用nexta,b表示子串Sa,b的下一个相同子串的开始位置,则只需要O(L2)的空间方块消除n个带颜色方格排成一列，相同颜色的方块连成一个区域（如果两个相邻方块颜色相同，则这两个方块属于同一区域）游戏时，你可以任选一个区域消去。设这个区域包含的方块数为x，则将得到x2分方块消去之

14、后将产生空列,此时其右边的所有方块就会向左移,直到所有方格连在一起方块消除下面是一个游戏的例子分析输入表示成两个长度为L的数组color和lenL表示有多少“段”不同的颜色方块colori表示第i段的颜色leni表示第i段的方块长度题目的例子成color=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；如果和前面的若干段一起消，设这“若干段

15、”中最后面的那一段是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个关口的车最少会与多少辆巡逻车相遇

16、，以及在此情况下到达第n个关口的最早时刻。所有车辆到达关口的时刻必须是整秒。分析di,T表示在时刻T到达第i个关口的途中与巡逻车最少相遇次数，状态转移方程为函数wi-1,T-t,T是目标车于时刻T-t从第i-1个关口出发，于时刻T到达第i个关口途中与巡逻车相遇的次数设每两个关口间行驶时间有k种选择,状态总数为O(kn2)，决策数目为O(k)，转移时间依赖于w分析方法一：方法一：在每个决策中都进行一次计算，对所有从第i个关口出发的巡逻车进行判断，由于每辆巡逻车恰好被判断一次，故这样每个状态的计算w的平均时间复杂度为O(m/n)，算法总时间复杂度为O(kn2)O(k)O(m/n)=O(k2nm)。

17、方法二：方法二：仔细观察状态转移方程可以发现，在对状态di,T进行转移时，所计算的函数w都是从第i个关口出发的，而且出发时刻都是T，只是相应的到达时刻不同。能否考虑这些车之间的联系，从而利用已经得出的结果，减少重复运算呢？分析令gk=wi,T,k+1-wi,T,k,设到达时间为k和k+1的目标车分别为车A和车B对于每辆从第i个关口出发的巡逻车C，设其出发和到达时刻分别为St和Tt，则Ttk+1，车A车B与车C的相遇情况相同Tt=k，则车A与车C相遇，车B的分析又分为，若St=T，则车B不与车C相遇，否则车B也与车C相遇Tt=k+1,则车B与车C相遇，对车A的分析又分为，若St=T，则车A不与车

18、C相遇，否则车A也与车C相遇分析综合起来gk=G(Tt=k+1)&(St=T)G(Tt=k)&(St=T)G(P)表示所有从关口i出发且满足条件P的巡逻车数目计算di,T时先对所有从第i个关口出发的巡逻车进行一次扫描,求出wi,T,T+300的同时求出gT+301.T+600，时间复杂度为O(m/n)以后的转移中，由wi,T,k+1=wi,T,k+gk，仅需O(1)时间就可以求出函数值w，状态转移时间仅为O(1)总时间O(kn2)*(O(m/n)+k*O(1)=O(knm+k2n2)由于n50,m300，方法二比方法一快得多并行期望值考虑一个可以并行执行两个高级语言程序的机器。高级语言程序由若

19、干条赋值指令组成，形式是：:=op 变量名由不超过20个字母组成。运算数是变量名或小于100的正整数。op是运算符，可以是加号“+”或者减号“-”执行前,程序被翻译成机器语言。X:=Y+Z翻译成Mov R1,YMov R2,ZAdd R1,R2Mov X,R1Mov指令把第二个操作数送到第一个中去，Add操作进行加法，并把结果保存在第一个操作数中。注意Y和Z代表变量或者整数常量。X:=Y-Z 的机器语言代码类似并行期望值处理器接受了两个机器语言程序后，每次随机选一个程序，执行它的下一条指令。如果某个程序执行完毕，处理器会连续把另一个程序执行完。两个程序共享所有变量（一开始的时候各个变量的值均为

20、0），但拥有两个独立的寄存器R1和R2由于执行顺序不确定，最后各个变量的值也是不确定的。不过，可以计算出每个变量在所有情况下最终值的平均数（即并行期望值）。现在给你两个高级语言程序，请编程算出所有变量的并行期望值。每个高级语言程序最多有25条指令，两个程序最多共使用10个变量。分析首先把高级语言程序翻译成机器语言,翻译规则:=+:=+:=op :=+其中x是程序代号.即一共有四个寄存器:R11,R12,R21,R22,和普通变量同等对待dx,y,k表示程序1执行完x条指令,程序2执行完y条指令后变量k的并行期望值分析情况一:刚刚执行完第1个程序的第x条指令该指令不是在给k赋值,等于dx-1,y

21、,k指令形如:=op,等于dx-1,y,a op dx-1,y,b记这个结果为K1情况二:刚刚执行完的是第2个程序的第y条指令,按同样的方法可计算出K2情况一的概率是x/(x+y),情况二是y/(x+y)按期望公式,dx,y,k=(x*K1+y*K2)/(x+y)分析为什么在情况一的赋值语句后,k的期望等于dx-1,y,a op dx-1,y,b?期望的线性性质为什么情况一的概率是x/(x+y),情况二是y/(x+y)?状态(x-1,y)和(x,y-1)的概率比为到达两个状态的路径条数比,即C(x+y-1,x-1)/C(x+y-1,y-1),展开得(x+y-1)!/(x-1)!y!/(x+y-

22、1)!/x!(y-1)!=x/y高性能计算机一个大型计算任务可以划分成很多A类任务和B类任务.所有A类任务都相同,所有B类任务都相同.所有任务的相对执行顺序没有要求有p个计算结点,对于第i个结点三种工作状态：待机、A类和B类。初始为待机状态，从其他的状态转入A或B状态分别需要tiA和tiB的时间连续处理x个A类子任务，时间为t=kiAx2；类似定义kiB你需要进行任务分配,即给每个结点设置任务队列.队列中一串连续的同类子任务不能被分成两部分执行。所有结点都同时开始运行，目标是最后结束计算的结点的完成时间尽可能早分析该问题可以分成两个子问题：计算第i个结点完成ai个A任务和bi个B任务的最短时间

23、给第i个结点分配ai个A任务和bi个B任务，取所有结点运行时间的最大值问题1的解决:让di,t,a,b表示结点i，还有a种A任务和b种B任务，并且当前需要执行t类任务（t=A或B）所需要的最短时间分析决策为当前执行j个连续序列,di,A,a,b=mindi,B,a-j,b+tiA+kiA*j2问题1的解fi,a,b=mindi,A,a,b,di,B,a,b问题2是任务分配问题.gi,a,b代表前i个结点完成a个A任务b个B任务的最短时间，决策为给任务i分配j个A任务和k个B任务,即gI,a,b=min maxdi-1,a-j,b-k,fi,j,k 时间O(pna2nb2),空间O(nanb),

24、如何优化?模板匹配*代表零个或多个字符。通配符Q称两个通配符P1和P2的公共模板，如果被Q匹配的字符串一定同时被二者匹配。如ba*ab是*ab*和ba*b的公共模板P1、P2的一个模板集合Q1，Q2，Qn称为完备的，如果每个Qi都是P1、P2的公共模板，且任何一个既能被P1匹配又能被P2匹配的字符串至少能被一个Qi匹配给出P1，P2，求模板数目最少的完备模板集合例如，对于ba*ab和*ab*，一个包含最少数目模板的完备集合为：ba*ab*b,bab*b,ba*ab,bab 分析如果把一个模板看作一个集合（即它能匹配到所有字符串集合），则模板包含关系等同于集合包含关系本题的任务是求P1和P2的交

25、集的最小覆盖(即这些集合的并为P1和P2的交,且集合数目应尽量小)基本思想:枚举每一个种同时被两个模板匹配的串s，对每种情况都构造一个模板去覆盖它分析令子问题(i,j)表示需要匹配P1从第i位起的剩下串和P2从第j位起的剩下串，状态转移有四种情况：a*和b*没有交集，因为无论公共串s的第一位是什么都不行。a*b和ab*有交集，且公共串s的第一位只有一种情况：a，剩下的任务是要让s从第2位起同时匹配*b和b*。转移到(i+1,j+1)。a*b和*ab有交集，且s的第一位必须是a。显然对于P1来说还需要匹配*b，但是对于P2来说，可以匹配ab，也可以匹配*ab，甚至可以匹配b。则(i,j)转化为了

26、(i+1,j)、(i+1,j+1)和(i+1,j+2)*ab和*b有交集，且s的第一位随便是什么都可以，用*表示（想一想，为什么）。现在状态转移到了什么地方呢？是(i+1,j)和(i,j+1)好象有点乱.仔细分析后两种情况,*可以看为空或者吃掉一个字符不可解码的编码给定n(n20)个01编码串S1,S2,Sn，寻找一个编码串T，至少可被分解为两种不同的Si的排列例如：给定5个01编码串：S1=0110，S2=00，S3=111，S4=001100，S5=110。一个符合要求的编码串T是：001100110，两种分解方法为00+110+0110(S2+S5+S1)001100+110(S4+S5

27、)而0110110只有一种分解方法 0110+110(S1+S5)寻找长度最短的符合要求的编码串T，若有多个符合要求的最短编码串T，则输出字典顺序最小的分析先考虑搜索策略。搜索的关键是编码串T至少存在两种不同的分解方法。从搜索分解方法出发，同时搜索两种分解方法，可以大大减少搜索量。分析不完整的分解方案所无法匹配的剩余部分，一定是某个S编码串的后缀。定义状态di,j为：当B部分为第i个数字串从第j+1开始的后缀时，A部分部分的最短长度边界:当存在某个长度为j的串为串i的前缀时di,j=j,其他di,j为无穷大分析转移和A无关,只考虑B.从某个状态di,j出发进行转移，可以分为两种情况：某串k是B

28、的前缀，则用di,j+Lk更新di,j+LkB是某串k的前缀,则用di,j+Li-j更新dk,Li-j最后的解是所有dk,Lk 中最小的一个分析因为题目要求找出的串是长度最短且在同长度的串中字典序最小的一个，因此，若长度不等时，可以直接取小的那个；若长度相等，则要追溯前面的状态，取字典序较小的那个。这与一般的动态规划是不太相同的，需要特别注意为了编程方便，可以采用记忆化搜索的方式。另外，由于程序中需要大量用到查找某个字符串是否存在的操作，为了提高程序效率，可以用Trie的结构来存储青蛙的烦恼池塘里有n片荷叶（1n1 000），它们正好形成一个凸多边形。按照顺时针方向将这n片荷叶顺次编号为1，2

29、，n。有一只小青蛙站在1号荷叶上，它想跳过每片荷叶一次且仅一次（它可以从所站的荷叶跳到另外任意一片荷叶上）。同时，它又希望跳过的总距离最短。请你编程帮助小青蛙设计一条路线。分析最短的路线中不存在相交的边。证明:路线变换（实线表示一步到达，虚线多步）根据这个结论可以知道：从1出发第一步只能到2或者n。如果第一步到了2，则第二步只能到n或者3，因为边不能相交！分析任意时刻没有经过的顶点构成区间设ds,L,0表示从s出发，遍历ss+L-1中的顶点一次且仅一次的最短距离；ds,L,1表示从s+L-1出发，遍历ss+L-1中的顶点一次且仅一次的最短距离。容易写出状态转移方程,时空均为O(n2)排列问题在

30、整数1，2，N的排列中，有些排列满足性质A：该排列中除了最后一个整数以外的每一个整数后面都跟有（不必直接紧跟）一个同它相差为1的整数。例如：N=4，排列1432是具有性质A的，而2431则不满足。设有一个N个数的排列，已知其中P(PN)个位置上的数，求共有多少个这样的排列在P个位置上具有已知的数，且具有上述性质A。例如：N=4，且已知第1位、第2位分别是1和4，则1432，1423就是这样的两个排列。分析通过枚举N比较小的时候满足题目的排列，发现一个规律：任何一个排列的后k位 （lkn）是若干连续整数组成的集合。可以用数学归纳法证明这个结论进一步地，还可以证明只要满足任意后k位（lkn）是若干

31、连续整数组成的集合，则这个排列一定符合题目要求。下面给出时空复杂度均为O(n2)的算法 分析设ds,r表示满足下面条件的序列C的总数为s,s+1s+r-1的一个排列任意后k位都是连续整数组成的集合如果原问题中倒数第i个位置上的数已经确定为x（lir），那么C的倒数第i个位置上的数也要是x。由加法原理得 最优排序二叉树边长为3的正三角形分成三层共9个小的正三角形，把它们从顶到底，从左到右以19编号。边长为n的正三角形可以划分成n2个单位三角形。四个这样的边长为n的正三角形可以组成一个三棱锥。将正三棱锥的三个侧面依顺时针次序(从顶向底视角)编号为A,B,C，底面编号为D。右图为展开图，圆点为该面的

32、顶最优排序二叉树把这A、B、C、D四个面各自划分成n2个单位三角形,并把14n2分别填入四个面总共4n2个单位三角形中。现在要求你编程求由单位三角形组成的最大排序二叉树。对于任一单位三角形，可选它三个相邻(有公共边的三角形相邻)的单位三角形中任意一个作为父结点，其余两个分别作为左孩子和右孩子。当然，做根结点的单位三角形不需要父结点，而左孩子和右孩子对于二叉树中的任意结点来说并不是都必须的。最优排序二叉树举例给出四面上的数如下图则最优排序二叉树如右图分析设di,j,k为根是i,结点范围为jk时的最大排序二叉树结点个数i有三个邻居可以作i的子树的根,但不在j,k范围内的结点是不能选的.考虑i所有能

33、选的邻居u,根据u和i的关系可唯一确定它是i的左子树还是右子树.状态转移时,取左子树和右子树各自的最大值并相加即可结点范围的设立自然的排除了把父亲选作儿子的情况,也避免了两棵子树的交叉分析状态有三维,似乎是O(n6)的,但其中一维取决于i的父亲,因此只需要记录i的父亲是它的第几个邻居状态数是O(n2)的(单位三角形有4n2个),状态转移时间O(n2),总时间O(n4).空间也是O(n4)的提示:用记忆化搜索来实现本题的动态规划可以大大降低编程复杂度 Bugs公司Bugs公司生产一种23单位尺寸的高科技芯片嵌入NM（N150,M10）单位尺寸的模板内，损坏的单位小方格已被标上黑色记号芯片内不能有

34、黑色记号，同时芯片与芯片不能重叠。将尽量多的芯片嵌入模板分析M=10,可以考虑信息压缩的动态规划定义基线Bi,j为前i-1列和第i列前j行组成的图形,若从右往左从下往上处理,则Bi,j为考虑格子(i,j)时的剩余棋盘剩余棋盘分析剩余棋盘Bi,j上能切下多少芯片要取决于Bi,j已经有哪些格子被占用了用(0,2,1,0,2)表示每行已经被占了几个格子(注意:如果占了左边的格子,右边也不能用)分析把占用情况看成3进制数,则有3M种情况设di,j,P为Bi,j的占用情况为P时最多能嵌入的芯片数,转移方式:忽略;放2*3;放3*2.下图为处理到深灰色格时选择放置3*2分析状态有MN3M个,转移为O(1)

35、的,总时间复杂度为O(MN3M)空间复杂度为O(MN3M),但可以用滚动数组优化,即只保存相邻三列的占用情况，降为O(M3M)，可以承受优化:很多P是不可能出现的,因为只有2*3和3*2两种芯片,无法产生单独的一列占用迷宫统计Jimmy自己办了一个游园活动，其中一个项目是让游客去走一个随机生成的m行n列(1m5,1n6)的迷宫，迷宫里有空地，也有障碍物（每个障碍物恰好占一个方格）。游客总是从左上角走到右下角，每次可以往东南西北四个方向之一行走迷宫的生成方式很简单：每一个格子都有一个独立的概率p，表示该格子为障碍物的概率。如果程序生成了一个无解的迷宫，它会重新生成一个。你的任务是计算每个格子成为

36、一个有解迷宫中的障碍物的概率。分析m和n都很小,是否可以随便做呢?m=n=5时有解迷宫有1,225,194个m=5,n=6时高达30,754,544个如果把所有有解迷宫都列举出来再计算概率，需要花费约10分钟的时间。思路：不列举所有有解迷宫，而是把这些迷宫分成若干个不相交的集合，在每个集合中分别计算概率分析考虑像经典的信息压缩动态规划一样,一列一列递推需要知道当前列（或者多列）的哪些信息?如果只是简单的保存是否有障碍的信息,保存一列、两列或者三列都可能不够。如果全部保存完，就没有意义了。怎么办呢？分析只记录当前列的每个格子是否能和起点连通也是不对的，因此即使当前某个格子和起点不连通，以后也是可

37、能连通的。这样做在状态转移的时候遇到了困难正确的做法是记录当前列y中每两个格子每两个格子是否连通方法一：方法一：每两个格子用01表示，一共m2/2个格子对，共2m*m/2种状态，太大方法二：方法二：记录每个格子(x,y)的Px值，0表示它和起点连通，否则它表示同列中与该格连通的所有格子的最小行编号（如果没有这样的格子，则Px=x）。这样状态最多(m+1)!个，可以承受分析用S(i,P)表示共i列，最后一列的连通情况为P的所有迷宫集合为了统计和各个格子相关的概率，需要增加一维b，用di,P,b表示S(I,P)中最后一列第b个格子为障碍的迷宫总概率,为了方便b=0表示总概率b的选择有mn+1种,P

38、的元素有(m+1)!个分析这样，每次进行状态转移时，枚举当前列的所有(m+1)!(mn+1)种状态和2m种决策（下一列的障碍情况），状态转移的时候需要做BFS，但是由于只需要用上一列的P值和新列，因此BFS时间2m+1当i、P和决策一定时只需要BFS一次即可计算出新的P，因此对于所有b,计算di,P,b的总时间为2m(2m+1+mn+1)=O(2mmn)分析(i,P)状态有n*(m+1)!个，因此总时间为n(m+1)!*O(2mmn)=O(mn22mm!)。显然和m有关的项比n大得多，因此总认为当m大于n时交换m,n，并把矩阵翻转。可以用滚动数组，空间是O(m+1)!mn)的贪吃的九头龙有N个

39、果子的果树，每个树枝都有一个难受值把果子分成M份，每份给一个头吃。每个头至少吃一个果子，大头必须吃果子1，且一共吃K个同一个头吃的果子如果有树枝相连，增加难受值。让总难受值尽量小分析如果果子不够吃（即NC(i)时状态di,j没有意义链的情形：不需要枚举决策完全二叉树：合法状态只有O(N)个快乐的蜜月宾馆有一间蜜月房非常舒适,经理在每年年底都会收到第二年的所有蜜月房预订单。第i中预订单包括：到达日期Si、离去日期Ti和费用Ci不与任何其他预订要求发生冲突的预订单必然会被接受;对于其他订单,任两份的时间都不能重叠你的任务是在所有合法方案中找出获利第k(k=100)大的方案.当然，可能有若干种方案的

40、获利是一样大的。假如有3种方案的收入同时为3，有2种方案的收入为2，则收入为3的方案都属于获利最大，收入为2的方案都属于获利第二大。所有的住、离店登记都在中午12点进行。共有r个预订要求(r20,000)分析首先考虑k=1的情况.由于天数比较小(最多366天),因此设di为前i天可到达的最大收益,Si为右端点在i的线段集.有两类转移不选取Si的任何线段,为di-1选取某条左端点为j,权值为w的线段,为dj+w时间复杂度为O(D+r),因为所有订单恰好被考虑一次,其中D为一年的天数分析前i天收益前k大的方案,前j天(j i)天也是前k大的,因此每个阶段需要保留前k大的方案设di,k为前i天第k大

41、的方案,每次考虑某条左端点为j的线段x时,设数组gk=dj,k+w,与di,k归并取前k的元素每考虑一条线段的时间复杂度为O(k),因此总时间复杂度为O(D+kr)移动机器人在二维网格上有许多机器人。每个机器人的状态由(x,y,d)表示,即位置和朝向(东南西北).每个机器人按照各自各自固定的指令执行移动,两个机器人互不影响，同一个位置可以有多个机器人。指令有两种,转身(左转90，180或270度)和移动(按当前朝向移动一个单位)在机器人开始移动前，可以去掉一些指令，改变机器人的行动路线和最终位置。删除最少的指令让所有机器人到达同一个最终位置指令数不超过50分析首先求出每个机器人能到达的范围和每

42、个点需要删除的最少指令分析每个机器人的指令数目不大于50，这就将机器人活动的范围限制以初始位置为中心，边长为50的正方形中。机器人的位移用二元组(x,y)(-50 x,y50)表示，方向合起来表示一个状态。设di,x,y,k表示前i条指令执行后到达状态(x,y,k),需要最少删除多少条指令用更新法做状态转移,决策是O(1)的(删还是不删),时间O(n2),R个机器人共O(Rn2)分析然后再求出最优点.每次求交集,去掉不可能的点,同时记录剩下点需要删除的指令最小值,处理完所有机器人即可求交集的方法可以用增量法,逐个判断集合i是否在前i-1个集合的交中方法一:用排序二叉树,查找和删除都是O(log

43、n)的方法二:用二维数组记录第1个机器周围的n2个格子是否在集合中,查找和删除都是O(1)的最终时间复杂度为O(Rn2)佳佳的筷子中国人吃饭喜欢用筷子。佳佳与常人不同，他的一双筷子有三只，一双短筷子加上一根比较长的（一般用来穿香肠之类的食物）。两只较短的筷子的长度应该尽可能接近，但是最长的那根长度是无所谓的。如果一双筷子的长度分别是A，B，C(ABC)，则用(A-B)2的值表示这双筷子的质量，这个值越小，这双筷子的质量越高。佳佳请朋友吃饭，并准备为每人准备一双这种特殊的筷子。佳佳有N（N5 000）只筷子，他希望找到一种办法搭配好K双筷子，使得这些筷子的质量值和最小分析任一副筷子中A和B一定长

44、度相邻.证明如下对于某副筷子（A1,B1,C1）和另一副筷子（A2,B2,C2），如果A1=A2=B1=B2，那么交换一下筷子重新组合成（A1,A2,C1）和（B1,B2,C2）质量和会更优。对于某副筷子（A,B,C）和闲置的筷子D，如果A=D=3j的时候状态是合法的。状态转移方程为时间复杂度为(NK)偷懒的工人人们都说A公司的工人很勤劳，因为只要一有可以做的工作，他们马上就会去做，而不会出现有任务可以完成，但他却闲着没事干的情况。虽然话说得没错（因为公司有这个规定），但是工人们实际上是很懒的，他们希望在符合公司规定的前提下让自己的工作时间尽量短。假设某工人有n个任务要做，第i个任务恰好需要t

45、i单位的时间才能完成，而且必须在时间区间ai,di被执行（即任务的开始时刻不小于ai，结束时刻不大于di,tdi-ai2ti）。假设该工作在同一时间只能进行同一个任务，而同一个任务要么不做，要么在规定的期限内不间断的做。他应该怎样选择任务，才能让自己的工作时间尽量少呢？分析如果用di代表i时刻以后还需要工作的最少时间，如何状态转移?我们不知道哪些任务是已经完成了的（因为它们执行时间不确定），因此决策集合无法确定好在有条件 t=di-ai2ti。当完成一个任务以后，严格的时间期限已经不可能允许工作再重复选择这个任务了,因此i可以唯一确定可以进行的任务集合分析如果用di代表i时刻以后还需要工作的最

46、少时间,Ti表示此时刻可以进行的工作集合,则状态转移有两类Ti为空:等于di+1Ti不为空:对Ti中的任务j,取mindi+tj+tj用记忆化搜索可以避免无意义的递推计算铁路调度铁路上的某些地方设有火车站。站内往往设有一些从主干线分叉出去的铁路支路，供火车停靠。支路有长度，火车也有长度，且每列火车长度相等某东西向的铁路上有一小站。该站只有一条铁路支路可供火车停靠，并且该铁路支路最多能够容纳M辆火车（M3）。该站只允许火车自东方进站，自西方出站，且先进站的火车必须先出站每天都有N辆（N250）自东方驶向西方的火车要求在预定时刻进站，并作一定时间的停靠。小站工作人员必须阅读所有火车的进站申请，并决

47、定接受那些火车的申请。火车进站、出站的用时忽略不计，因此小站允许几辆火车同时进站或出站，且小站工作人员可以任意安排火车进站的先后排列次序,原则是尽量多地满足申请火车的要求平板涂色用预定的颜色给一块布满不同尺寸互不覆盖的矩形平板涂色。每个刷子涂一种不同的颜色C只能在所有紧靠在它上方的矩形涂色后才能涂色。矩形F必须在矩形C和D后涂色。每个矩形必须立刻涂满，不得只涂一部分求拿起刷子的次数最少的涂色方案。如图，至少要把刷子拿起来3次，平板的左上角坐标总是(0,0)，坐标范围是099，矩形不超过15个道路重建农夫John的农场有n(n150)个牛舍，有些牛舍之间有双向道路连接，而每两个牛舍之间有且仅有一

48、条通路（因此可以表示成一棵树）。由于任意一场地震都很可能让John的农场变得不连通，因此John希望估计一下，至少需要毁坏多少条道路才会让一个恰好有 p(pn)个牛舍的子树脱离其他牛舍。道路重建在下面的例子中,要想让6个结点的子树孤立出来，只需要把14边和15边删掉就可以了。这样，1,2,3,6,7,8构成的子树和其他结点分离圆和多边形给你一个圆和圆周上的N个点。选择M个并按圆周上的顺序连成一个M边形，使面积最大。如下图，右上方的多边形最大铁球落地n(n100 000)个平台的上空有一个铁球。球每次落到某平台上以后，游戏者可以选择它左滚还是右滚，球滚动和下落的速度都是1。球每次的下落高度不能超过一个给定值MAX。设计策略使得球尽块落到地面而不被摔碎。假设地面高度为0且无限宽