搜索
《算法艺术与信息学竞赛》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】铁路调度索引•【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是规则序列，那么（S）和[S]也是规则序列；–如果A和B都是规则序列，那么AB也是规则序列。•例如，下面的字符串都是规则序列：–()，[]，(())，([])，()[]，()[()]•这几个则不是规则序列：–(，[，]，)(，([()•现在，给出一些由‘(’，‘)’，‘[’，‘]’构成的序列，请添加尽量少的括号，得到一个规则序列。分析•d[i,j]:子串i…j最少需要添加的括号数•状态转移–S形如(S’)或者[S’]:d[i+1,j-1]–S形如(S’或者[S’:d[i+1,j]+1–S形如S’)或者S’]:d[i,j-1]+1–长度大于1:d[i,k]+d[k+1,j](i=k=j-1)•状态O(n2),转移O(n),共(n3)棋盘分割•将一个8×8的棋盘进行如图所示的分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有n（n15）块矩形棋盘（每次切割都只能沿着棋盘格子的边进行）。棋盘分割•原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘，并使各矩形棋盘总分的均方差最小。(a)允许的分割方案(b)不允许的分割方案分析•变形均方差公式•平均值是一定的（等于所有方格里的数的和除以n）•只需要让每个矩形总分的平方和尽量小21211222)(1)2)((1xxnxxxxnnniiniinii分析•考虑左上角坐标为(x1,y1)，右下角坐标为(x2,y2)的棋盘，设它把切割k次以后得到的k+1块矩形的总分平方和最小值为d[k,x1,y1,x2,y2]•状态转移:沿着某横线切或者竖线切，然后选一块继续切,如横着切的两类决策是–d[k-1,x1,y1,a,y2]+s[a+1,y1,x2,y2]–d[k-1,a+1,y1,x2,y2]+s[x1,y1,a,y2]–其中x1=a=x2分析•状态d[k,x1,y1,x2,y2]•设m为棋盘边长，则状态数目为m4n，决策数目为O(m)•转移时间取决于计算s[x1,y1,x2,y2]的时间•预处理先用O(m2)时间算出左上角为(1,1)的所有矩阵元素和，这样状态转移时间就是O(1)，总的时间复杂度为O(m5n)决斗•编号为1~n的n个人按逆时针方向排成一圈，他们要决斗n-1场。每场比赛在某相邻两人间进行，败者退出圈子，紧靠败者右边的人成为与胜者直接相邻的人。•任意两人之间决斗的胜负都将在一矩阵中给出（如果A[i,j]=1则i与j决斗i总是赢，如果A[i,j]=0则i与j决斗时i总是输），•求出所有可能赢得整场决斗的人的序号分析•d[i,j]表示是否有可能i和j相遇,则第i个人能取得最后的胜利当且仅当d[i,i]为true•状态转移:考虑相遇前的最后一步,则d[I,j]为true当且仅当–能找到一个k,使得i能遇k,k能遇到j,且–i或者j能打败k•状态有O(n2)个,转移有O(n)个,共O(n3)跳舞机•DDR的主要内容是用脚来踩踏板。踏板有4个方向的箭头，用1，2，3，4来代表•每首歌曲有一个箭头序列，游戏者必须按照这个序列依次用某一只脚踩相应的踏板。在任何时候，两只脚都不能在同一个踏板上，但可以同时待在中心位置0。跳舞机•每一个时刻，必须移动而且只能移动一只脚去踩相应的箭头，另一只脚不许移动。•跳DDR会消耗体力。从中心移动到任何一个箭头耗费2单位体力，从任何一个箭头移动到相邻箭头耗费3单位体力，移动到相对的箭头（1和3相对，2和4相对）耗费4单位体力，而留在原地再踩一下只需要1单位。•给定一首舞曲,每个箭头应该用哪只脚踩才能使体力消耗最少呢？例如对于序列LLUR,用LLRR脚去踩，总的体力耗费为2+1+2+3=8单位分析•目前左脚在位置x,右脚在位置y,从第k个箭头开始跳,最少体力耗费为d[x,y,k],则–用左脚,d[a[k],y,k+1]+effort(x,a[k])–用右脚,d[x,a[k],k+1]+effort(y,a[k])•状态是O(n)的，决策是O(1)的,总时间复杂度为O(n)积木游戏•有N块编号依次为1，2，…，N的长方体积木。每块积木有三条不同边分别称为a、b、c边•从积木中选出若干块分成M堆,每堆至少有1块积木，并且第K堆中任意一块积木的编号要大于第K+1堆中任意一块积木的编号bac积木游戏•每一堆积木要垂直摞成一根柱子,并满足–除最顶上的一块积木外，任意一块积木的上表面同且仅同另一块积木的下表面接触，并且要求下面积木的上表面能包含上面的积木的下表面，也就是说，要求下面积木的上表面两对边的长度分别大于等于上面积木两对边的长度。–对于任意两块上下表面相接触的积木，下面积木的编号要小于上面积木的编号•要求每堆积木的高度和尽量大分析•我们从最后一堆积木开始,一个个积木考虑•记d[i,a,b,k]为已经用了前a个积木得到了i根柱子,目前顶面为积木b的第k个面,以后还能获得的最大高度,有三类决策–新起一堆,d[i+1,a+1,a+1,k’],当im时合法–加在当前堆,d[i,a+1,a+1,k’],当放得上时合法–丢弃当前块,d[i,a+1,b,k],随时合法•状态O(n2m)个,决策O(1),总时间O(n2m)艺术馆的火灾•艺术馆着火了.这是一幢两层的小楼，每层有N个房间，用两个数分别表示艺术品价值和火势.•灭火器最多只能发射K次，每次发射将覆盖一个矩形的区域（矩形的高度可以是1也可以是2），所到之处不但火焰会被扑灭，艺术品也被摧毁。•你需要决定灭火器每次应该怎样发射，才能将这次火灾的损失降到最低限度。损失等于摧毁的艺术品总价值加上剩余的火势总值40/5050/4030/5060/7030/4030/5040/2020/30分析•模型：在一个2×N的矩阵中，找出K个子矩阵。矩阵的每个元素有两个值V和F。题目要让K个子矩阵的V值和其他矩阵的F值之和最小，而如果我们令W=V-F，则目标转换为让K个子矩阵元素的W值之和最小•矩阵可以重叠，这给解题带来不便。我们可以不考虑重叠情况，如图所示图1-43重叠情况转化为不重叠情况LRS(1,2,2,4)S’(1,3,1,6)LRS(1,2,2,4)S’(1,5,1,6)分析•用区域(i,j)来表示“第一行第i个格子右边所有元素加上第二行第j个格子右边的所有元素”这个区域，用d[s,i,j]来表示在这个区域中选择s个子矩阵，它们的元素总和的最小值•状态转移的决策是新矩形的放置,有三类–第一行第i个格子不用,d[s,i+1,j]–在第一行从第i个格子开始放矩形,设长度为L,转移到d[s-1,i+L,j]–i=j时还可放置宽度为2的矩形,转移到d[s-1,i+L,j+L]•状态O(kn2)个,决策O(n),转移时间O(1)(先预处理),总时间O(kn3)机器人的名字•考虑一种基于重复子串的压缩方法•用[St]k表示k个相同的子串St(其中St称为重复子串，k是一个单字节整数，只占一个字符位置)•如果这k个子串并没有连在一起，则可以在[St]k的后面加上{S1}t1{S2}t2…{Sr}tr（1tik，titi+1），表示在第ti个St的后面放置Si，Si称为插入子串•St和Si也都可以是压缩后的字符串•比如I_am_WhatWhat_is_WhatWhat的压缩结果为I_am_[What]4{_is_}2，长度为19(例子中的空格用下划线“_”表示，数字2和4实际上是用单字节二进制表示的)•名字不会以空格开始或结尾，大小写敏感分析•令d[a,b]表示以a,b为起止位置的串(记为S[a,b])的最短压缩长度,则目标为d[1,L]•状态转移–连接:d[a,b]=min{d[a,i]+d[i+1,b]},a=ib–压缩:需要确定重复子串.当重复子串很多时,决策枚举的代价较大•压缩决策可以通过动态规划来枚举!分析•g[a,b,c]表示将串S[a,b],选择长度为c的重复子串进行压缩得到的最短长度.枚举插入串(可能为空)的下一个位置i,状态转移方程为caiicadcbigcaicbigcbagciiScaaScbica3]1,[],,[],,[min],,[]1,[]1,[1分析•边界条件•d[a,b]的状态转移方程•如何较快的判断是否有S[a,a+c-1]=S[i,i+c-1]?从c=1开始递推,总O(L3)13],[],1[]1,[121],,[abcbadbcbScaaSabcabcbag或者11min{[,][1,]}[,]minmin{[,,]}aibibadaidibdabgabi分析•时间:预处理O(L3),核心O(L4),共O(L4)•空间–g:本来是三维的O(L3)的,但注意到在每个式子里b参量没有发生变化,故以b为阶段递推,只需要O(L2)的空间–预处理结果:如果用h[a,b,c]表示是否有S[a,a+c-1]=S[b,b+c-1],则又是三维的.可以用链式存储,用next[a,b]表示子串S[a,b]的下一个相同子串的开始位置,则只需要O(L2)的空间方块消除•n个带颜色方格排成一列，相同颜色的方块连成一个区域（如果两个相邻方块颜色相同，则这两个方块属于同一区域）•游戏时，你可以任选一个区域消去。设这个区域包含的方块数为x，则将得到x2分•方块消去之后将产生空列,此时其右边的所有方块就会向左移,直到所有方格连在一起方块消除•下面是一个游戏的例子分析•输入表示成两个长度为L的数组color和len–L表示有多少“段”不同的颜色方块–color[i]表示第i段的颜色–len[i]表示第i段的方块长度•题目的例子成color={1,2,3,1},len={1,4,3,1}•用(i,j,k)表示在第i~j段方块的右边添加k个颜色为color[j]的方块后得到的方块序列,相当于考虑第i~j段,但让len[j]的值增加k分析•d[i,j,k]表示把序列(i,j,k)消除的最大得分•考虑最后一段，有两类决策–如果马上消掉，就是d[i,j-1,0]+(len[j]+k)2；–如果和前面的若干段一起消，设这“若干段”中最后面的那一段是p(i=pj)，得分为d[i,p,k+len[j]]+d[p+1,j-1,0],其中color[p]=color[j]•边界条件