《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】佳佳
2、的筷子 【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序
3、列 【AOA】最优布车方案括号序列 定义如下规则序列（字符串）： 空序列是规则序列； 如果S是规则序列，那么（S）和S也是规则序列； 如果A和B都是规则序列，那么AB也是规则序列。 例如，下面的字符串都是规则序列： ()， ， ()， ()， ()， ()() 这几个则不是规则序列： (， ， ， )(， () 现在，给出一些由(，)，构成的序列，请 添加尽量少的括号，得到一个规则序列。 分析 di,j: 子串ij最少需要添加的括号数 状态转移 S形如(S)或者S: di+1,j-1 S形如(S或者S: di+1,j+1 S形如S)或者S: di,j-1+1 长度大于1: di,k+dk+1,
4、j (ik+1，车A车B与车C的相遇情况相同 Tt=k，则车A与车C相遇，车B的分析又分为， 若St := op 变量名由不超过20个字母组成。运算数是变量名或小于 100的正整数。op是运算符，可以是加号“+”或者减号“-” 执行前, 程序被翻译成机器语言。X := Y + Z翻译成 Mov R1, Y Mov R2, Z Add R1, R2 Mov X, R1 Mov指令把第二个操作数送到第一个中去，Add操作进行 加法，并把结果保存在第一个操作数中。注意Y和Z代表 变量或者整数常量。X := Y - Z 的机器语言代码类似并行期望值 处理器接受了两个机器语言程序后，每次随机选 一个程序
5、，执行它的下一条指令。如果某个程序 执行完毕，处理器会连续把另一个程序执行完。 两个程序共享所有变量（一开始的时候各个变量 的值均为0），但拥有两个独立的寄存器R1和R2 由于执行顺序不确定，最后各个变量的值也是不 确定的。不过，可以计算出每个变量在所有情况 下最终值的平均数（即并行期望值）。现在给你 两个高级语言程序，请编程算出所有变量的并行 期望值。每个高级语言程序最多有25条指令，两 个程序最多共使用10个变量。 分析 首先把高级语言程序翻译成机器语言, 翻译规则 := + := + := op := + 其中x是程序代号. 即一共有四个寄存器: R11, R12, R21, R22,
6、和普通变量同等对待 dx,y,k表示程序1执行完x条指令, 程序2执行完y 条指令后变量k的并行期望值分析 情况一: 刚刚执行完第1个程序的第x条指令 该指令不是在给k赋值, 等于dx-1,y,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? 期望的线性性质 为什么情
7、况一的概率是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-1)!/x!(y-1)!=x/y高性能计算机 一个大型计算任务可以划分成很多A类任务和B类 任务. 所有A类任务都相同, 所有B类任务都相同. 所有任务的相对执行顺序没有要求 有p个计算结点, 对于第i个结点 三种工作状态：待机、A类和B类。初始为待机状态， 从其他的状态转入A或B状态分别需要tiA和tiB的时间 连续处理x个A类子任务，时间为t =
8、 kiAx2；类似定义kiB 你需要进行任务分配, 即给每个结点设置任务队列 . 队列中一串连续的同类子任务不能被分成两部分 执行。所有结点都同时开始运行，目标是最后结 束计算的结点的完成时间尽可能早分析 该问题可以分成两个子问题： 计算第i个结点完成ai个A任务和bi个B任务的最 短时间 给第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
9、 问题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), 如何优化?模板匹配 *代表零个或多个字符。通配符Q称两个通配符P1 和P2的公共模板，如果被Q匹配的字符串一定同 时被二者匹配。如ba*ab是*ab*和ba*b的公共模板 P1、P2的一个模板集合Q1，Q2，Qn称为完备 的，如果每个Qi都是P1、P2的公共模板，且任何
10、一个既能被P1匹配又能被P2匹配的字符串至少能 被一个Qi匹配 给出P1，P2，求模板数目最少的完备模板集合 例如，对于ba*ab和*ab*，一个包含最少数目模板 的完备集合为：ba*ab*b, bab*b, ba*ab, bab 分析 如果把一个模板看作一个集合（即它能匹 配到所有字符串集合），则模板包含关系 等同于集合包含关系 本题的任务是求P1和P2的交集的最小覆盖( 即这些集合的并为P1和P2的交, 且集合数目 应尽量小) 基本思想: 枚举每一个种同时被两个模板匹 配的串s，对每种情况都构造一个模板去覆 盖它分析 令子问题(i,j)表示需要匹配P1从第i位起的剩下串和P2从第 j位起的
11、剩下串，状态转移有四种情况： 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)转化为了(i+1,j)、(i+1,j+1)和(i+1,j+2) *ab和*b有交集，且s的第一位随便是什么都可以，用*表示（想一 想，为什么）。现在状态转移到了什么地方呢？是(i+1,j)和(i,j+1) 好象有点乱
12、. 仔细分析后两种情况, *可以看为空或者吃掉 一个字符不可解码的编码 给定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) 而0110110只有一种分解方法 0110+110 (S1+S5) 寻找长度最短的符合要求的编码串T，若有多个符 合要求的最短编码串T，则输出字典顺序最小的分析 先考虑搜索策
13、略。搜索的关键是编码串T至 少存在两种不同的分解方法。从搜索分解 方法出发，同时搜索两种分解方法，可以 大大减少搜索量。分析 不完整的分解方案所无法匹配的剩余部分，一定 是某个S编码串的后缀。 定义状态di,j为：当B部分为第i个数字串从第j+1 开始的后缀时，A部分的最短长度 边界: 当存在某个长度为j的串为串i的前缀时 di,j=j, 其他di,j为无穷大分析 转移和A无关, 只考虑B. 从某个状态di,j出 发进行转移，可以分为两种情况： 某串k是B的前缀，则用di,j+Lk更新di,j+Lk B是某串k的前缀, 则用di,j+Li-j更新dk,Li-j 最后的解是所有dk,Lk 中最小
14、的一个分析 因为题目要求找出的串是长度最短且在同长度的 串中字典序最小的一个，因此，若长度不等时， 可以直接取小的那个；若长度相等，则要追溯前 面的状态，取字典序较小的那个。这与一般的动 态规划是不太相同的，需要特别注意 为了编程方便，可以采用记忆化搜索的方式。另 外，由于程序中需要大量用到查找某个字符串是 否存在的操作，为了提高程序效率，可以用Trie 的结构来存储青蛙的烦恼 池塘里有n片荷叶（1n1 000），它们正 好形成一个凸多边形。按照顺时针方向将 这n片荷叶顺次编号为1，2，n。 有一只小青蛙站在1号荷叶上，它想跳过每 片荷叶一次且仅一次（它可以从所站的荷 叶跳到另外任意一片荷叶上
15、）。同时，它 又希望跳过的总距离最短。 请你编程帮助小青蛙设计一条路线。 分析 最短的路线中不存在相交的边。证明: 路线 变换（实线表示一步到达，虚线多步） 根据这个结论可以知道：从1出发第一步只 能到2或者n。如果第一步到了2，则第二步 只能到n或者3 ，因为边不能相交！ 分析 任意时刻没有经过的顶点构成区间 设ds,L,0表示从s出发，遍历ss+L-1中 的顶点一次且仅一次的最短距离； ds,L,1表示从s+L-1出发，遍历ss+L-1 中的顶点一次且仅一次的最短距离。 容易写出状态转移方程, 时空均为O(n2)排列问题 在整数1，2，N的排列中，有些排列满足性 质A：该排列中除了最后一个整数以外的每一个 整数后面都跟有（不必直接紧跟）一个同它相差 为1的整数。例如：N = 4，排列1432是具有性质 A的，而2431则不满足。 设有一个N个数的排列，
