动态规划10页.pptVIP

括号序列 定义如下规则序列（字符串）： 空序列是规则序列； 如果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块矩形棋盘，并使各矩形棋盘总分的均方差最小。 分析 变形均方差公式 平均值是一定的（等于所有方格里的数的和除以n） 只需要让每个矩形总分的平方和尽量小 分析 考虑左上角坐标为(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总是输）， 求出所有可能赢得整场决斗的人的序号 分析 f[i,j]表示是否有可能i和j相遇, 则第i个人能取得最后的胜利当且仅当f[i,i]为true 状态转移: 考虑相遇前的最后一步, 则f[I,j]为true当且仅当 能找到一个k, 使得i能遇k, k能遇到j, 且 i或者j能打败k 状态有O(n2)个, 转移有O(n)个, 共O(n3) F[I,j]=(f[I,k] and f[k,j]) and (A[I,k] or A[j,k]),ikj 跳舞机 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堆中任意一块积木的编号 积木游戏 每一堆积木要垂直摞成一根柱子,并满足 除最顶上的一块积木外，任意一块积木的上表面同且仅同另一块积木的下表面接触，并且要求下面积木的上表