《浙江大学-acm程序设计竞赛-动态规划讲义》由会员分享，可在线阅读，更多相关《浙江大学-acm程序设计竞赛-动态规划讲义（74页珍藏版）》请在金锄头文库上搜索。
1、动态规划专题讲义 前言 本文只是个人对动态规划的一些见解 理论性并不一定能保证正确 有不足和缺漏之处请谅解和及时地指出 动态规划 是信息学竞赛中选手必须熟练掌握的一种算法 他以其多元性广受出题者的喜爱 动态规划 目录 什么是动态规划状态阶段决策一种确立状态的方法两种简单的动规武器三种特殊的动态规划 什么是动态规划 在学习动态规划之前你一定学过搜索 那么搜索与动态规划有什么关系呢 我们来下面的一个例子 back 数字三角形 给你一个数字三角形 形式如下 12345678910找出从第一层到最后一层的一条路 使得所经过的权值之和最小或者最大 back 数字三角形 无论对与新手还是老手 这都是再熟悉
2、不过的题了 很容易地 我们写出状态转移方程 f i j a i j min f i 1 j f i 1 j 1 对于动态规划算法解决这个问题 我们根据状态转移方程和状态转移方向 比较容易地写出动态规划的循环表示方法 但是 当状态和转移非常复杂的时候 也许写出循环式的动态规划就不是那么简单了 解决方法 back 记忆化搜索 记忆化搜索 我们尝试从正面的思路去分析问题 如上例 不难得出一个非常简单的递归过程 f1 f i 1 j 1 f2 f i 1 j iff1 f2thenf f1 a i j elsef f2 a i j 显而易见 这个算法就是最简单的搜索算法 时间复杂度为2n 明显是会超时
3、的 分析一下搜索的过程 实际上 很多调用都是不必要的 也就是把产生过的最优状态 又产生了一次 为了避免浪费 很显然 我们存放一个opt数组 back 记忆化搜索 Opt i j 每产生一个f i j 将f i j 的值放入opt中 以后再次调用到f i j 的时候 直接从opt i j 来取就可以了 于是动态规划的状态转移方程被直观地表示出来了 这样节省了思维的难度 减少了编程的技巧 而运行时间只是相差常数的复杂度 而且在相当多的情况下 递归算法能更好地避免浪费 在比赛中是非常实用的 记忆化的功效 back 动态规划的实质 可以看出动态规划的实质就是这也就是为什么我们常说动态规划必须满足重叠子
4、问题的原因 记忆化 正符合了这个要求 记忆化搜索 状态阶段决策 或许有一种对动态规划的简单称法 叫分阶段决策 其实我认为这个称法并不是很能让人理解 那么下面我们来看看阶段 状态 决策这三者间得关系吧 back 状态阶段决策 状态是表现出动态规划核心思想的一个东西 而分阶段决策这个东西有似乎没有提到状态 这是不科学的 阶段 有些题目并不一定表现出一定的阶段性 数字三角形的阶段就是每一层 这里我们引入一个概念 以前状态 但阶段不是以前状态 状态是阶段的表现形式 数字三角形的以前状态就是当前层的前一层 那什么是决策呢 我们看看下面一张图就知道了 back 决策 当前状态 以前状态 决策 显然 从上图
5、可以看出 当前状态通过决策 回到了以前状态 可见决策其实就是状态之间的桥梁 而以前状态也就决定了当前状态的情况 数字三角形的决策就是选择相邻的两个以前状态的最优值 back 动规的要诀 状态 我们一般在动规的时候所用到的一些数组 也就是用来存储每个状态的最优值的 我们就从动态规划的要诀 也就是核心部分 状态 开始 来逐步了解动态规划 back 拦截导弹 拦截导弹 Noip2002 某国为了防御敌国的导弹袭击 发展出一种导弹拦截系统 但是这种导弹拦截系统有一个缺陷 虽然它的第一发炮弹能够到达任意的高度 但是以后每一发炮弹都不能高于前一发的高度 某天 雷达捕捉到敌国的导弹来袭 由于该系统还在试用阶
6、段 所以只有一套系统 因此有可能不能拦截所有的导弹 输入导弹依次飞来的高度 计算这套系统最多能拦截多少导弹 拦截导弹 状态的表示 f i 表示当第i个导弹必须选择时 前i个导弹最多能拦截多少 每个导弹有一定的高度 当前状态就是以第i个导弹为最后一个打的导弹 以前状态就是在这个导弹以前打的那个导弹 显然这是十分能够体现状态间的联系的题目 back 最长公共子串 给出两个字符串序列 求出这样的一个最长的公共子串 子串中的每个字符都能在两个原串中找到 而且每个字符的顺序和原串中的顺序一致 交错匹配 交错匹配 最长公共子串的改编 给你两排数字 只能将两排中数字相同的两个位置相连 而每次相连必须有两个匹
7、配形成一次交错 交错的连线不能再和别的交错连线有交点 问这两排数字最多能形成多少个交错匹配 233241513510312324121553 状态的表示 f i j 表示前i个第一排的数字和前j个第二排的数字搭配的最优值 当前的状态就是当前你枚举到的一组交错的后面两个位置 例如上图中当前状态是3和1 第一组交错 枚举他的以前状态就有13 这样在13之前会有一个最优值存在 因此可以由此得到31的最优值 back 买车票 买车票 Ural1031 Ekaterinburg城到Sverdlovsk城有直线形的铁路线 两城之间还有其他一些停靠站 总站数为N 各站按照离Ekaterinburg城的距离编
8、号 Ekaterinburg城编号为1 Sverdlovsk城编号为N back 买车票 某两站之间车票价格由这两站的距离X决定 当0 X L1时 票价为C1元 当L1 X L2时 票价为C2元 当L2 X L3时 票价为C3元 当两站距离大于L3时没有直达票 所以有时候要买几次票做几次车才行 比如 在上面的例图中 2 6没有直达票 有几种买票方法可以从2 6 其中一种是买C2元的2 3车票 再买C3元的3 6车票 back 买车票 给定起点站和终点站还有L1 L2 L3 C1 C2 C3 求出要从起点到终点最少要花多少钱 怎么办 确定题目的当前状态与以前状态 back 买车票 当前状态 以前
9、状态 当前所在的某个车站 这一题的以前状态其实只有3种 即满足3种距离 收费 情况的3个车站 要知道这3个车站可以先做一个预处理 显然这3个车站在满足距离限制的条件下应该越远越好 back 买车票 预处理很容易想出一个N 2的预处理 但是那样是会超时的 由于尽量要让车站离得远 费用是一样的啊 因此在每种收费情况下 每个车站的以前状态车站一定是递增的序列 这里是只要O N 的程序 forj 1to3dobegink en 1 fori endowntobedobeginwhile way i way k be dodec k p i j k 1 end end 数组P i j 表示的是I状态的第
10、j种以前状态 back 买车票 动态规划的部分fori be 1toendo 枚举当前状态 begincost i maxlongint forj 1to3do 枚举以前状态 beginif p i j i and cost i cost p i j c j thencost i cost p i j c j end end back 动规的要诀 状态 有时候当前状态确定后 以前状态就已经确定 则无需枚举 back Tom的烦恼 Tom是一个非常有创业精神的人 由于大学学的是汽车制造专业 所以毕业后他用有限的资金开了一家汽车零件加工厂 专门为汽车制造商制造零件 由于资金有限 他只能先购买一台加
11、工机器 现在他却遇到了麻烦 多家汽车制造商需要他加工一些不同零件 由于厂家和零件不同 所以给的加工费也不同 而且不同厂家对于不同零件的加工时间要求不同 有些加工时间要求甚至是冲突的 但开始和结束时间相同不算冲突 Tom当然希望能把所有的零件都加工完 以得到更多的加工费 但当一些零件的加工时间要求有冲突时 在某个时间内他只能选择某种零件加工 因为他只有一台机器 为了赚得尽量多的加工费 Tom不知如何进行取舍 Tom的烦恼 Tom的烦恼按结束时间排序 枚举结束时间作为当前状态 以前状态就是该结束时间对应的起始时间 这是已经确定的 back 文字游戏 文字游戏 fairfox邀请赛1 给你一份单词表
12、 和一个句子 求出该句子能有多少中不同的划分方法 例如 单词是abcdabcd句子是abcd他共有4种完全划分方案 ab cda b c da b cdab c d 当前状态就是单词在句子中向后靠的位置 以前状态就是确定这个单词位置以后 除掉这个单词长度后的一个位置 状态转移方程是 F i F i F i length word j IOI中有一题 前缀 也是类似的题目 决策中的定量 状态转移方程的构造无疑是动态规划过程中最重要的一步 也是最难的一步 对于大多数的动态规划 寻找状态转移方程有一条十分高效的通道 就是寻找变化中的不变量 定量处理的过程也就是决策实施的过程 寻找定量 back 寻找
13、定量 最佳加法表达式有一个由1 9组成的数字串 问如果将m个加号插入到这个数字串中 使得所形成的算术表达式的值最小 Problem 或许你不明白我在说什么 那么我们通过题目来说明吧 back 最佳加法表达式 这一题中的定量是什么呢 因为是添入加号 那么添完加号后 表达式的最后一定是个数字串 这就是定量 从这里入手 不难发现可以把以前状态认为是在前i个字符中插入k 1个加号 这里的i是当作决策在枚举 然后i 1到最后一位一定是整个没有被分割的数字串 第k个加号就添在i与i 1个数字之间 这样就构造出了整个数字串的最优解 而至于前i个字符中插入k 1个加号 这又回到了原问题的形式 也就是回到了以前
14、状态 所以状态转移方程就能很快的构造出来了 back 最佳加法表达式 用f i j 表示的是在前i个字符中插入j个加号能达到的最小值 最后的答案也就是F length s m 于是就有一个动规的方程 F i j min f i j f k j 1 num k 1 i num k 1 i 表示k 1位到i位所形成的数字 这里显然是把加号插入了第k 1个位置上 知道了这一题怎么做以后 乘积最大的一题也是完全一样的形式 谁还会去用搜索 back 定量 现在大概大家已经了解了定量是什么 那么我们下面通过几道题目来了解一下定量的威力 back 游戏 游戏 Noip2003普及组 这一题的描述简单说一下
15、在一个圈的周围有n个石子 将他们划分成m堆 每堆中的石子必须连续相邻 每一堆石子计算出他们的总重量mod10的值 然后将这些值相乘 求得到的结果最大最小值是多少 back 游戏 这一题作者其实是根据最佳加法表达式改编的 但是他加了一个在圈上的条件 怎么办呢 寻找定量 back 游戏 可想而知 因为至少要分成1堆 那么至少有两个石子之间是会被分隔开的 这就是定量 当划分数 1时 一定有两个相邻石子被划分到不同的堆里去 于是这个圈被这样的理解断成了一条线 解法就和最佳加法表达式一样了 当然这个断开的位置是需要枚举的 然后保留下一个最优值 显然这个断开的操作对整个过程没有影响 因为这是必然的情况 这
16、是定量 back 最优三角形划分 问题描述给定一具有N N 50 个顶点 从1到N编号 的凸多边形 每个顶点的权均已知 问如何把这个凸多边形划分成N 2个互不相交的三角形 使得这些三角形顶点的权的乘积之和最小 back 最优三角形划分 这一题大概搜都是十分麻烦的 可是这一题Dp的话 比搜索要容易实现和容易理解得多 先得表示一下状态 我们用f i j 表示以第i个点开头 顺时针长度为j的一块子多边形 如上图中f 1 5 表示的子多边形 黑色虚线划开 back 最优三角形划分 如果没有红色虚线的部分 或许你会认为决策应该是枚举子多边形内的两点连线 然后分成两个子多边形 这显然是不行的 因为计算机已经无法再表示分割出来的子多边形了 不能用f i j 来表示了 back 最优三角形划分 那么我们该如何决策呢 寻找定量 显然可以发现 f i j 表示的子多边形有一条边是在内部的 黑色虚线 而这一条边在该子多边形内必定属于某个三角形 因为我们选择了该子多边形作为一种状态 那么就一定存在那条虚线黑边 所以一定存在所说的三角形 于是我们枚举这个三角形的另外一个点在子多边形的位置 则可以把子问题还原到原
