跳舞机
• DDR的主要内容是用脚来踩 踏板。踏板有4个方向的箭 头，用1，2，3，4来代表 • 每首歌曲有一个箭头序列， 游戏者必须按照这个序列依 次用某一只脚踩相应的踏板。 在任何时候，两只脚都不能 在同一个踏板上，但可以同 时待在中心位置0。
跳舞机
• 每一个时刻，必须移动而且只能移动一只 脚去踩相应的箭头，另一只脚不许移动。 • 跳DDR会消耗体力。从中心移动到任何一 个箭头耗费2单位体力，从任何一个箭头移 动到相邻箭头耗费3单位体力，移动到相对 的箭头（1和3相对，2和4相对）耗费4单位 体力，而留在原地再踩一下只需要1单位。 • 给定一首舞曲, 每个箭头应该用哪只脚踩才 能使体力消耗最少呢？例如对于序列LLUR, 用LLRR脚去踩，总的体力耗费为2 + 1 + 2 + 3 = 8单位
分析
• 模型：在一个2×N的矩阵中，找出K个子矩 阵。矩阵的每个元素有两个值V和F。题目 要让K个子矩阵的V值和其他矩阵的F值之和 最小，而如果我们令W=V-F，则目标转换 为让K个子矩阵元素的W值之和最小 • 矩阵可以重叠，这给解题带来不便。我们 可以不考虑重叠情况，如图所示
L L
R S(1,2,2,4) S’(1,3,1,6) S(1,2,2,4) S’(1,5,1,6) 图 1-43 重叠情况转化为不重叠情况
决斗
• 编号为1~n的n个人按逆时针方向排成一圈， 他们要决斗n-1场。每场比赛在某相邻两人 间进行，败者退出圈子，紧靠败者右边的 人成为与胜者直接相邻的人。 • 任意两人之间决斗的胜负都将在一矩阵中 给出（如果A[i,j]=1则i与j决斗i总是赢，如果 A[i,j]=0则i与j决斗时i总是输）， • 求出所有可能赢得整场决斗的人的序号
索引
• • • • • • • • 【UVAxxx】最长上升子序列问题 【UVAxxx】最优二分检索树问题 【POJ1180】任务调度问题 【AOA】序列分割问题 【AOA】多排列的LCS 【POJ1159】回文词 【AOA】友好城市 【POJ1160】邮局
索引
• • • • • 【AOA】基因串 【POJ1946】奶牛转圈 【AOA】元件折叠 【AOA】 DNA序列 【AOA】最优布车方案
《算法艺术与信息学竞赛》 45道动态规划题目
刘汝佳
索引
• • • • • • • • 【POJ1141】括号序列 【POJ1191】棋盘分割 【SPOJ196】决斗 【AOA】跳舞机 【AOA】积木游戏 【AOA】艺术馆的火灾 【AOA】机器人的名字 【UVa10559】方块消除
索引
• • • • • • • • 【AOA】公路巡逻 【POJ1074】并行期望值 【AOA】高性能计算机 【AOA】模板匹配 【AOA】不可解码的编码 【AOA】青蛙的烦恼 【AOA】排列问题 【AOA】最优排序二叉树
– 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)的空间
– (， [， ]， )(， ([()
• 现在，给出一些由‘(’，‘)’，‘[’，‘]’构成的序 列，请添加尽量少的括号，得到一个规则序列。
分析
• 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(kn2)个, 决策O(n), 转移时间O(1)(先预处理), 总时间O(kn3)
机器人的名字
• 考虑一种基于重复子串的压缩方法 • 用[St]k表示k个相同的子串St(其中St称为重复子串， k是一个单字节整数，只占一个字符位置) • 如果这k个子串并没有连在一起，则可以在[St]k的 后面加上{S1}t1{S2} t2…{Sr} tr（1<ti<k，ti<ti+1）， 表示在第ti个St的后面放置Si，Si称为插入子串 • St和Si也都可以是压缩后的字符串 • 比如I_am_WhatWhat_is_WhatWhat的压缩结果 为I_am_[What]4{_is_}2，长度为19 (例子中的空 格用下划线“_”表示，数字2和4实际上是用单字 节二进制表示的) • 名字不会以空格开始或结尾，大小写敏感
索引
• • • • • • • • 【POJ1038】 Bugs公司 【UVa10531】迷宫统计 【AOA】贪吃的九头龙 【AOA】快乐的蜜月 【AOA】移动机器人 【UVa10271】佳佳的筷子 【AOA】偷懒的工人 【AOA】铁路调度
索引
• • • • • • • • 【POJ1691】平板涂色 【POJ1947】道路重建 【ZJUxxx】圆和多边形 【AOA】铁球落地 【UVA10118】免费糖果 【AOA】丢三落四的老鼠 【AOA】最长公共子序列问题 【UVA10635】排列的LCS问题
• 原棋盘上每一格有一个分值，一块矩形棋 盘的总分为其所含各格分值之和。现在需 要把棋盘按上述规则分割成n块矩形棋盘， 并使各矩形棋盘总分的均方差最小。
(a) 允许的分割方案
(b) 不允许的分割方案
分析
• 变形均方差公式
n n 1 1 n 2 2 ( n( x ) 2 x i 2 2 x x i ) x i ( x ) 2 n n i 1 i 1 i 1
• 平均值是一定的（等于所有方格里的数的 和除以n） • 只需要让每个矩形总分的平方和尽量小
分析
• 考虑左上角坐标为(x1,y1)，右下角坐标为 (x2,y2)的棋盘，设它把切割k次以后得到的 k+1块矩形的总分平方和最小值为 d[k,x1,y1,x2,y2] • 状态转移: 沿着某横线切或者竖线切，然后 选一块继续切, 如横着切的两类决策是
• 状态O(n2), 转移O(n), 共(n3)
ቤተ መጻሕፍቲ ባይዱ
棋盘分割
• 将一个8×8的棋盘进行如图所示的分割： 将原棋盘割下一块矩形棋盘并使剩下部分 也是矩形，再将剩下的部分继续如此分割， 这样割了(n-1)次后，连同最后剩下的矩形 棋盘共有n（n<15）块矩形棋盘（每次切割 都只能沿着棋盘格子的边进行）。
棋盘分割
括号序列
• 定义如下规则序列（字符串）：
– 空序列是规则序列； – 如果S是规则序列，那么（S）和[S]也是规则序列； – 如果A和B都是规则序列，那么AB也是规则序列。
• 例如，下面的字符串都是规则序列：
– ()， []， (())， ([])， ()[]， ()[()]
• 这几个则不是规则序列：
积木游戏
• 有N块编号依次为1，2，…，N的长方体积木。每 块积木有三条不同边分别称为a、b、c边
a c
b
• 从积木中选出若干块分成M堆, 每堆至少有1块积 木，并且第K堆中任意一块积木的编号要大于第 K+1堆中任意一块积木的编号
积木游戏
• 每一堆积木要垂直摞成一根柱子,并满足
– 除最顶上的一块积木外，任意一块积木的上表 面同且仅同另一块积木的下表面接触，并且要 求下面积木的上表面能包含上面的积木的下表 面，也就是说，要求下面积木的上表面两对边 的长度分别大于等于上面积木两对边的长度。 – 对于任意两块上下表面相接触的积木，下面积 木的编号要小于上面积木的编号
分析
• 边界条件
g[a, b, c] d [ a , b ] 3 b a 1 2 c b a 1 或者 S[a, a c 1] S[b c 1, b] c b a 1
• d[a,b]的状态转移方程
分析
• g[a,b,c]表示将串S[a,b], 选择长度为c的重复 子串进行压缩得到的最短长度. 枚举插入串 (可能为空)的下一个位置i, 状态转移方程为
g[i, b, c] i a c g[a, b, c] min a c i b c 1 g[i, b, c] d[a c, i 1] 3 i a c S [ a ,a c 1] S [i ,i c 1]
分析
• 令d[a,b]表示以a, b为起止位置的串(记为 S[a,b])的最短压缩长度, 则目标为d[1,L] • 状态转移
– 连接: d[a,b] = min{d[a,i] + d[i+1,b]}, a<=i<b – 压缩: 需要确定重复子串. 当重复子串很多时, 决策枚举的代价较大
• 压缩决策可以通过动态规划来枚举!
min{d[a, i] d[i 1, b]} a i b d[a, b] min 1min1{g[a, b, i]} i b a
• 如何较快的判断是否有S[a, a+c-1]=S[i, i+c-1]? 从c=1开始递推, 总O(L3)
分析
• 时间: 预处理O(L3), 核心O(L4), 共O(L4) • 空间
• 状态O(n2m)个, 决策O(1), 总时间O(n2m)
艺术馆的火灾
• 艺术馆着火了. 这是一幢两层的小楼，每层有N个 房间，用两个数分别表示艺术品价值和火势.
40/50 30/40 50/40 30/50 30/50 40/20 60/70 20/30
• 灭火器最多只能发射K次，每次发射将覆盖一个 矩形的区域（矩形的高度可以是1也可以是2）， 所到之处不但火焰会被扑灭，艺术品也被摧毁。 • 你需要决定灭火器每次应该怎样发射，才能将这 次火灾的损失降到最低限度。损失等于摧毁的艺 术品总价值加上剩余的火势总值