资源描述：
《道动态规划题目分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
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也是规则序列。例如，下面的字符串都是规则序列：()，[]，(())，([])，()[]，()[()]这几个则不是规则序列：(，[，]，)(，([()现在，给出一些由‘(’，‘)’，‘[’，‘]’构成的序列，请添加尽量少的括号，得到一个规则序列。分析d[i,j]:子串i…j最少需要添加的括号数状态转移S形如(S’)或者[S’]:d[i+1,j-1]S形如(S’或者[S’:d[i+1,j]+1S形如S’)或者S’]:d[i,j-1]+1长度大于1:d[i,k]+d[k+1,j](i<=k<=j-1
4、)状态O(n2),转移O(n),共(n3)棋盘分割将一个8×8的棋盘进行如图所示的分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有n（n<15）块矩形棋盘（每次切割都只能沿着棋盘格子的边进行）。棋盘分割原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘，并使各矩形棋盘总分的均方差最小。分析变形均方差公式平均值是一定的（等于所有方格里的数的和除以n）只需要让每个矩形总分的平方和尽量小分析考虑左上角坐标为(x1,y1)，右下角坐标为(x2,y2)的棋
5、盘，设它把切割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)决斗
6、编号为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
7、的主要内容是用脚来踩踏板。踏板有4个方向的箭头，用1，2，3，4来代表每首歌曲有一个箭头序列，游戏者必须按照这个序列依次用某一只脚踩相应的踏板。在任何时候，两只脚都不能在同一个踏板上，但可以同时待在中心位置0。跳舞机每一个时刻，必须移动而且只能移动一只脚去踩相应的箭头，另一只脚不许移动。跳DDR会消耗体力。从中心移动到任何一个箭头耗费2单位体力，从任何一个箭头移动到相邻箭头耗费3单位体力，移动到相对的箭头（1和3相对，2和4相对）耗费4单位体力，而留在原地
