DP-线型动态规划.ppt

线型动态规划 长沙市雅礼中学朱全民 带权有向的多段图问题 给定一个带权的有向图 要求从点A到点D的最短路径 设F i 表示从点A到达点i的最短距离 则有F A 0F B1 5 F B2 2F C1 min F B1 3 8F C2 min F B1 2 F B2 7 7F C3 min F B2 4 6F D min F C1 4 F C2 3 F C3 5 10 多阶段最优化决策问题 由上例可以看出 整个问题分成了A B C D四个阶段来做 每个阶段的数值的计算只会跟上一个阶段的数值相关 这样一直递推下去直到目标 即由初始状态开始 通过对中间阶段决策的选择 达到结束状态 这些决策形成了一个决策序列 同时确定了完成整个过程的一条最优的活动路线 状态转移方程 设fk i k阶段状态i的最优权值 即初始状态至状态i的最优代价 fk 1 i min fk j u i j 第k 1阶段状态 第k阶段状态 决策 动态规划的基本原理 最优性原理作为整个过程的最优策略 它满足 相对前面决策所形成的状态而言 余下的子策略必然构成 最优子策略 无后效性原则给定某一阶段的状态 则在这一阶段以后过程的发展不受这阶段以前各段状态的影响 所有各阶段都确定时 整个过程也就确定了 这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展 这个性质称为无后效性 第1题 关键子工程 有N个子工程 每一个子工程都有一个完成时间 子工程之间的有一些依赖关系 即某些子工程必须在一些子工程完成之后才开工 在满足子工程间的依赖关系前提下 可以有任何多个子工程同时在施工 求整个工程的完成的最短时间 求出所有关键子工程 N 200 有向图的关键路径 分析 如果该图能够进行拓扑排序 证明有解 反之则无解 根据拓扑序列进行动态规划求解 得到工程所需的完成时间 设F I 表示完成子工程I所需的最早时间 动态规划方程 F I MAX F J A I J 根据的得到的F序列和拓扑序列 查找关键工程 初始时 最后完成的一个或多个工程为关键工程 如果F I F J A I J 且第I个子工程为关键工程 那么第J个子工程也是关键工程 时间复杂度为O N2 拦截导弹 给定N个数求最长的不上升子序列长度求最少有多少个不上升序列能覆盖所有的数 即求最少覆盖序列 N 10000 分析 设f i 表示前i个数的最长不上升序列的长度 则 f i max f j 1 其中j a i 这里0 j i n 显然时间复杂度为O n2 上述式子的含义 找到i之前的某j 这个数不比第i个数小 对于所有的j取f j 的最大值 优化 分析样例这里找j 是在1 i之间进行寻找 那么我们能否快速查找到我们所要更改的j呢 要能更改需要两个条件 j a i f j 尽可能大以上两个条件提示我们后面的值一定要小于等于前面的值 因此我们试着构建一个下降的序列 在这个下降的序列中查找可以更改的f值 使得序列的值尽可能大 具体过程 思考 有些同学可能会问 对于每个f 为什么只保留一个数值呢 而对于该序列 为什么要保留较大的值呢 1 再回过头来看方程 f i max f j 1 其中j a i 该式子表示找前面的一个最大f的符合条件的j 因此只要保存符合条件的最大的j就可以了 在f值相同的情况下 保留较大的数显然更好 因为后面的数若能跟较小的数构成下降序列也一定能能较大的数构成下降序列 反之则不一定 例如207与300的f 2 但207不能与299构成下降序列 而300则可以 因为生成的序列为有序序列 因此我们可以采用二分查找的方法很快查找到更新的值 时间复杂度为O n n 求导弹的最小覆盖 第二问很容易想到贪心法 那就是采取多次求最长不上升序列的办法 然后得出总次数 上述贪心法不正确 很容易就能举出反例 例如 7541632 用多次求最长不上升序列所有为 75432 1 6 共3套系统 但其实只要2套 分别为 7541 与 632 那么 正确的做法又是什么呢 分析 上述问题的原因是若干次最优决策值和不一定能推导出整个问题的最优 为了解决这个问题下面介绍一个重要性质 最少链划分 最长反链长度为了证明这个性质 需要了解离散数学中偏序集的相关概念和性质以及偏序集的Dilworth定理 偏序集 偏序是在集合X上的二元关系 这只是个抽象符号 不是 小于或等于 它满足自反性 反对称性和传递性 即 对于X中的任意元素a b和c 有 自反性 a a 反对称性 如果a b且b a 则有a b 传递性 如果a b且b c 则a c 带有偏序关系的集合称为偏序集 令 X 是一个偏序集 对于集合中的两个元素a b 如果有a b或者b a 则称a和b是可比的 否则a和b不可比 一个反链A是X的一个子集 它的任意两个元素都不能进行比较 一个链C是X的一个子集 它的任意两个元素都可比 定理 在X中 对于元素a 如果任意元素b 都有a b 则称a为极小元 定理1 令 X 是一个有限偏序集 并令r是其最大链的大小 则X可以被划分成r个但不能再少的反链 其对偶定理称为Dilworth定理 令 X 是一个有限偏序集 并令m是反链的最大的大小 则X可以被划分成m个但不能再少的链 虽然这两个定理内容相似 但第一个定理证明要简单一些 此处就只证明定理1 证明 设p为最少反链个数 1 先证明X不能划分成小于r个反链 由于r是最大链C的大小 C中任两个元素都可比 因此C中任两个元素都不能属于同一反链 所以p r 2 设X1 X A1是X1中的极小元的集合 从X1中删除A1得到X2 注意到对于X2中任意元素a2 必存在X1中的元素a1 使得a1 k 由于X被划分成了k个反链 因此r k p 3 因此r p 定理1得证 解决 要求最少的覆盖 按照Dilworth定理最少链划分 最长反链长度所以最少多少套系统 最长导弹高度上升序列长度 知道了怎样求最长不上升算法 同样也就知道了怎样求最长上升序列 时间复杂度O n n 青蛙过河 NOIP2005 在河上有一座独木桥 一只青蛙想沿着独木桥从河的一侧跳到另一侧 在桥上有一些石子 青蛙很讨厌踩在这些石子上 由于桥的长度和青蛙一次跳过的距离都是正整数 我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点 0 1 L 其中L是桥的长度 坐标为0的点表示桥的起点 坐标为L的点表示桥的终点 青蛙从桥的起点开始 不停的向终点方向跳跃 一次跳跃的距离是S到T之间的任意正整数 包括S T 当青蛙跳到或跳过坐标为L的点时 就算青蛙已经跳出了独木桥 题目给出独木桥的长度L 青蛙跳跃的距离范围S T 桥上石子的位置 你的任务是确定青蛙要想过河 最少需要踩到的石子数 输入文件 输入文件river in的第一行有一个正整数L 1 L 109 表示独木桥的长度 第二行有三个正整数S T M 分别表示青蛙一次跳跃的最小距离 最大距离 及桥上石子的个数 其中1 S T 10 1 M 100 第三行有M个不同的正整数分别表示这M个石子在数轴上的位置 数据保证桥的起点和终点处没有石子 所有相邻的整数之间用一个空格隔开 输出文件 输出文件river out只包括一个整数 表示青蛙过河最少需要踩到的石子数 样例输入 1023523567 样例输出 2 数据规模 对于30 的数据 L 10000 对于全部的数据 L 109 分析 由于不能往回跳 很容易想到用动态规划解决这个题目 设f i 表示跳到第i个点需要踩到的最少石子数 则很容易写出动态规划的状态转移方程 时间复杂度是O L T S 但本题的L高达109 根本无法承受 进一步分析 我们先来考虑这样一个问题 长度为k的一段没有石子的独木桥 判断是否存在一种跳法从一端正好跳到另一端 若S MaxK 都可以从一端正好跳到另一端 题设中1 S T 10 经过简单推导或者程序验证就可以发现 取MaxK 100就能满足所有区间 于是我们可以分两种情况讨论 1 S T时 这时候由于每一步只能按固定步长跳 所以若第i个位置上有石子并且imodS 0那么这个石子就一定要被踩到 这是我们只需要统计石子的位置中哪些是S的倍数即可 复杂度O M 2 SMaxK 2 T 我们就将这段区域缩短成长度为MaxK 2 T 可以证明处理之后的最优值和原先的最优值相同 如上图所示 白色点表示连续的一长段长度大于MaxK 2 T的空地 黑色点表示石子 设原先的最优解中 白色段的第一个被跳到的位置a 最后一个被跳到的位置是b 则在做压缩处理之后 a和b的距离仍然大于MaxK 由上面的结论可知 必存在一种跳法从a正好跳到b 而且不经过任何石子 所以原来的最优解必然在处理之后的最优解解集中 经过这样的压缩处理 独木桥的长度L 最多为 M 1 MaxK 2 T M 大约12000左右 压缩之后再用先前的动态规划求解 复杂度就简化成了O L T S 已经可以在时限内出解了 这样本题就得到了解决 火车进站 给定N辆火车第i辆火车的进站时间arrive i 第i辆火车的离站时间leave i 车站只能容纳M辆火车求最多能接受多少辆火车 M 3 先看样第1 2 3辆分别进入 123 第2辆离开 可以看出要离开时 被第1辆火车卡在前面 因此第1辆火车不能进入 队列为 23 第2辆离开 第4辆进入 34 第3 4辆离开 队列空第5 6辆进入 56 第5 6分别离开 队列空因此答案为5辆 分析 按到达时间排序和离开时间排序 这样每一辆火车用线段描述 有 排在前面的火车 其进站时间必须先于排在后面的火车 排在前面的火车 其出站时间必须先于排在后面的火车 否则该列火车就要先进后出 不满足队列特点 这样对于任一列排序后的火车i 只有排在其后的火车才有可能在它出站之后进站 接下来的任务便是采用动态规划方法求解了 m 1时 设f i 表示第i列火车进站时 其后的火车最多可以进站的数量 则有 f j max f i 1 满足i比j先进站 且j在i出站之后进站 m 2 设f i j 表示车站停靠i j两列火车 i j 时 其后的火车 包括i j本身 最多可以进站的数量 则 f j k max f i j 1 条件 必须满足按i j k顺序进站和出站 另外还要满足k在i出站后进站 m 3 设f i j k 表示车站停靠i j k三列火车 i j k 时 其后的火车 包括i j k 最多可以进站的数量 则有 f j k l max f i j k 1 条件 必须满足按i j k l顺序进站和出站 另外还要满足l在i出站后进站 求最长公共子序列 给定的字符序列X x0 x1 xm 1 序列Y y0 y1 yk 1 是X的子序列 存在X的一个严格递增下标序列 使得对所有的j 0 1 k 1 有xij yj 例如 X ABCBDAB Y BCDB 是X的一个子序列 给出两个字串S1和S2 长度不超过5000 求这两个串的最长公共子串长度 分析样例 S1 ABCBDAB S2 BABCBD 可以看出他们的最长公共子串有ABCB ABCD BCBD等 长度为4 从样例分析 我们思考的方式为要找出S1串与S2串的公共子串 假设将S1固定 从第1个位置开始直到最后一个位置为止 与S2的各个部分不断找最长公共子串当然S1也可以变化 这样我们即得出了思路 枚举S1的位置i枚举S2的位置j找出S1的前i位与S2的前j位的最长公共子串 直到两个串的最后一个位置为止 动态规划 设f i j 表示S的前i位与T的前j位的最长公共子串长度 则有 时间复杂度O n m 主程序框架 n length a m length b fori 1tonbeginforj 1tomdobeginf j max f j 1 pf j 从前面的状态直接转移过来 if a i b j and pf j 1 1 f j then 多增加一位的情况 f j pf j 1 1 end pf f end 说明 pf是一个与f完全相同的数组 实现f i 与f i 1 的滚动 样例运行过程 S ABCBDAB T BABCBD 初始 f i 0 0 f 0 i 0 S 1 T 1 f 1 1 MAX f 1 0 f 0 1 0 S 1 T 2 f 1 2 MAX f 1 0 1 1 S 2 T 1 f 2 1 MAX f 1 0 1 1 S 2 T 2 f 2 2 MAX f 1 2 f 2 1 1 S 2 T 3 f 2 3 MAX f 1 2 1 2 S 3 T 1 f 3 1 MAX f 3 0 f 2 1 1 S 3 T 2 f 3 2 MAX f 2 2 f 3 1 1 S 3 T 3 f 3 3 MAX f 3 2 f 2 3 2 一直求到f 8 7 ans f 8 7 1 减1是因为最后都有一个 最短回文串 如果一个字符串正过来读和倒过来读是一样的 那么这个字符串就被称作回文串 例如abcdcba abcddcba就是回文串 而abcdabcd不是 任务 对于任意一个字符串 输出将这个字符串变为回文串需要插入的最少字符个数 比如 ab3bd只需要插入2个字符就可以变为一个回文串 0 n 1992 n为字符串长度 分析 ab3bd只需变为adb3bda即可 在前面插入d 在后面插入a 我们分几种情况讨论 若A形如 A 问号代表任意一个相同字符 下同 则只需将A变为回文串 若A形如 A再在A的后面插入一个 若A形如A 再在A的前面插入一个 动态规划 设f i j 为将Ai Aj变为回文串的最小代价 则一共有n2个状态 状态转移是O 1 的 总的复杂度为O n2 主程序 f i j 表示把i到j这一段变成回文需要最少添加多少字符 fori ndownto1doforj i 1tondobeginifs i s j then 不用添加 f i j f i 1 j 1 elsef i j maxint iff i j 1 1 f i j then 添加一个 f i j f i j 1 1 前插1个字符 iff i 1 j 1 f i j thenf i j f i 1 j 1 后插1个字符 end 总结 线型动态规划问题 最典型的特征就是状态都在一条线上 并且位置固定 问题一般都规定只能从前往后取状态 解决的办法是根据前面的状态特征 选取最优状态作为决策进行转移 设前i个点的最优值 研究前i 1个点与前i个点的最优值 利用第i个点决策转移 如下图 状态转移方程一般可写成 fi k min fi 1orj k u i j oru i i 1