动态规划专题讲义noip...ppt

动态规划专题讲义,前言,本文只是个人对动态规划的一些见解,理论性并不一定能保证正确,有不足和缺漏之处请谅解和及时地指出.,动态规划,是信息学竞赛中选手必须熟练掌握的一种算法,他以其多元性广受出题者的喜爱.,动态规划,目录,什么是动态规划状态阶段决策一种确立状态的方法两种简单的动规武器三种特殊的动态规划,什么是动态规划,在学习动态规划之前你一定学过搜索.那么搜索与动态规划有什么关系呢?我们来下面的一个例子.,back,数字三角形,给你一个数字三角形,形式如下:12345678910找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.,back,数字三角形,无论对与新手还是老手，这都是再熟悉不过的题了，很容易地，我们写出状态转移方程：f(i,j)=ai,j+minf(i-1,j)+f(i-1,j+1)对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么简单了。解决方法：,back,记忆化搜索,记忆化搜索,我们尝试从正面的思路去分析问题，如上例，不难得出一个非常简单的递归过程:f1:=f(i-1,j+1);f2:=f(i-1,j);iff1f2thenf:=f1+ai,jelsef:=f2+ai,j;显而易见，这个算法就是最简单的搜索算法。时间复杂度为2n，明显是会超时的。分析一下搜索的过程，实际上，很多调用都是不必要的，也就是把产生过的最优状态，又产生了一次。为了避免浪费，很显然，我们存放一个opt数组：,back,记忆化搜索,Opti,j-每产生一个f(i,j)，将f(i,j)的值放入opt中，以后再次调用到f(i,j)的时候，直接从opti,j来取就可以了。于是动态规划的状态转移方程被直观地表示出来了，这样节省了思维的难度，减少了编程的技巧，而运行时间只是相差常数的复杂度，而且在相当多的情况下，递归算法能更好地避免浪费，在比赛中是非常实用的.,记忆化的功效,back,动态规划的实质,可以看出动态规划的实质就是这也就是为什么我们常说动态规划必须满足重叠子问题的原因.记忆化,正符合了这个要求.,记忆化搜索,状态阶段决策,或许有一种对动态规划的简单称法,叫分阶段决策.其实我认为这个称法并不是很能让人理解.那么下面我们来看看阶段,状态,决策这三者间得关系吧.,back,状态阶段决策,状态是表现出动态规划核心思想的一个东西.而分阶段决策这个东西有似乎没有提到状态,这是不科学的.阶段,有些题目并不一定表现出一定的阶段性.数字三角形的阶段就是每一层.这里我们引入一个概念-以前状态.但阶段不是以前状态,状态是阶段的表现形式.数字三角形的以前状态就是当前层的前一层.那什么是决策呢?我们看看下面一张图就知道了.,back,决策,当前状态,以前状态,决策,显然,从上图可以看出,当前状态通过决策,回到了以前状态.可见决策其实就是状态之间的桥梁。而以前状态也就决定了当前状态的情况。,数字三角形的决策就是选择相邻的两个以前状态的最优值。,back,动规的要诀状态,我们一般在动规的时候所用到的一些数组，也就是用来存储每个状态的最优值的。我们就从动态规划的要诀，也就是核心部分“状态”开始，来逐步了解动态规划。,back,拦截导弹,拦截导弹（Noip2002）某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹。,拦截导弹,状态的表示fi，表示当第i个导弹必须选择时，前i个导弹最多能拦截多少。每个导弹有一定的高度，当前状态就是以第i个导弹为最后一个打的导弹。以前状态就是在这个导弹以前打的那个导弹。显然这是十分能够体现状态间的联系的题目。,back,最长公共子串,给出两个字符串序列。求出这样的一个最长的公共子串：子串中的每个字符都能在两个原串中找到，而且每个字符的顺序和原串中的顺序一致。,交错匹配,交错匹配（最长公共子串的改编）给你两排数字,只能将两排中数字相同的两个位置相连,而每次相连必须有两个匹配形成一次交错,交错的连线不能再和别的交错连线有交点.问这两排数字最多能形成多少个交错匹配.,233241513510312324121553,状态的表示fi,j表示前i个第一排的数字和前j个第二排的数字搭配的最优值。当前的状态就是当前你枚举到的一组交错的后面两个位置.例如上图中当前状态是3和1(第一组交错),枚举他的以前状态就有13.这样在13之前会有一个最优值存在,因此可以由此得到31的最优值.,back,买车票,买车票(Ural1031)Ekaterinburg城到Sverdlovsk城有直线形的铁路线。两城之间还有其他一些停靠站,总站数为N。各站按照离Ekaterinburg城的距离编号。Ekaterinburg城编号为1，Sverdlovsk城编号为N。,back,买车票,某两站之间车票价格由这两站的距离X决定.当0X=L1时，票价为C1元.当L1X=L2时，票价为C2元.当L21时,一定有两个相邻石子被划分到不同的堆里去!于是这个圈被这样的理解断成了一条线,解法就和最佳加法表达式一样了.当然这个断开的位置是需要枚举的,然后保留下一个最优值.显然这个断开的操作对整个过程没有影响,因为这是必然的情况,这是定量!,back,最优三角形划分,问题描述给定一具有N（N50）个顶点(从1到N编号）的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成N-2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？,back,最优三角形划分,这一题大概搜都是十分麻烦的,可是这一题Dp的话,比搜索要容易实现和容易理解得多.先得表示一下状态,我们用fi,j表示以第i个点开头,顺时针长度为j的一块子多边形.如上图中f1,5表示的子多边形(黑色虚线划开),back,最优三角形划分,如果没有红色虚线的部分,或许你会认为决策应该是枚举子多边形内的两点连线,然后分成两个子多边形.这显然是不行的,因为计算机已经无法再表示分割出来的子多边形了(不能用fi,j来表示了).,back,最优三角形划分,那么我们该如何决策呢?寻找定量!显然可以发现,fi,j表示的子多边形有一条边是在内部的(黑色虚线),而这一条边在该子多边形内必定属于某个三角形,因为我们选择了该子多边形作为一种状态,那么就一定存在那条虚线黑边,所以一定存在所说的三角形.于是我们枚举这个三角形的另外一个点在子多边形的位置,则可以把子问题还原到原问题(因为该三角形把多边形划成了两个可以用表示的多边形和一个三角形).这些再次分割出的子多边形就是以前状态,而刚才的多边形则是当前状态.,back,定量,其实定量的作用就是为了写出状态转移方程,即让人能迅速找出状态之间的关系(决策).通过定量的处理,当前状态又回到了以前状态,选手就可以知道,这一题就是要用动态规划来求解了.,back,定量,我们来看看刚才的一些题目的定量.交错匹配:一定存在最后一组交错(这好像是废话),所以枚举这个最后的交错的位置作为状态,这样就回到以前状态.买车票:定量1:一定有最后一个车站(这个作为状态);定量2:某个车站一定是由某个前面的车站到达的.(导弹拦截也是这样)数字三角形:某个点一定是由他上面的相邻两点到达的.(过河卒也是这样),定量很不错啊!,动态规划的武器,在动规的操作过程中,或者是操作过程前,有一些很常用的武器,这里简要介绍两种:,排序,填鸭,back,排序,武器一:排序遇到过很多需要排序的动态规划题目,如果不排序,动规的思想很难体现.,back,Tom的烦恼,Tom的烦恼这是大家熟知的一题,如果不排序的话,复杂度便是N2,按起始时间排序复杂度也是N2,二按结束时间排序之后复杂度降为了NlogN.,back,巴比伦塔,巴比伦塔问题描述:有很多的不同种类的立方体(长宽高不同),每一类有无限多个.将他们一层层的叠加起来,要求上面的一块立方体的下底面一定要比下面的一块立方体的上底面要小,就是长和宽都要小于.问最多能建成多高的塔.,back,巴比伦塔,经过研究可以发现,每一种类的立方体有3种不同的摆放方式,而每种摆放方式最多用1次,所以可以分离出3*N块“不同”的立方体,接下来,或许你仍然不知道如何动规,那么就试试排序.列出所有的石块的所有摆放方式xi,yi,zi.必须全部保证xiyi.然后按关键字xi,yi,zi的大小顺序排序.这样就可以进行十分简单的类似与导弹拦截的一个动态规划的处理了.限制条件是xi和yi,代价值是zi(高度).,back,滑雪,滑雪(上海2002)题目的大意是给出一个矩阵,如:,对于所给出的矩阵找出一条最长的递减链,满足链中相邻的两个元素间都是在矩阵中相邻的.上图中所给出的矩阵中的最长链是123425.,back,滑雪,对于有给出的数字进行递减排序,然后两重循环就搞定问题.动态转移方程是:Fi:=max(Fi,Fj+1);满足条件是i与j在原矩阵中相邻.试想,如果你不知道要排序,你能想到这题是用动态规划吗?,back,填鸭,武器二:填鸭这个思想带有枚举的感觉.就是开个大数组,把代价值一个个填进去.,back,硬币问题,硬币问题（经典问题）就是给出n种硬币的面值,问面值M有多少种不同的表示方法.动态转移方程是Fi:=Fi+FI-costj.当前状态是i,以前状态是i-costj.多米诺骨牌（某题的简化）有N张多米诺骨牌,每张的两端有两个数字,范围在1.6之间.每张骨牌可以正放,也可以反放.求出一种摆放的情况,使得所有的骨牌上端数字之和与下端数字之和的差值最小.求出最小差值.,back,多米诺骨牌,可以这么考虑这个问题:我们把每一个骨牌的上下差值记下。接下来的任务便是将这些值分成两组，使得他们的和的差值最小。动规过程如下：f0:=true;fori:=1tondoforj:=sumdowntoaidofj:=fjorfj-ai;Sum表示所有差值的和.ai表示第i块骨牌的差值.J是当前状态,j-ai是以前状态.fj表示j这个差值能否通过组合得到。接下来的程序就不用我多说了。,back,商店购物,商店购物(IOI)这一题更是需要开一个五维bool型数组.还需要通过递归求出组合形式.动规的方程我就不写了.,back,动态规划的武器,讲完了比较实用的两种种动规的武器之后,我们来看看一些大家可能不太会做的动规类型,特殊的动规,这里我讲讲三种特殊的动态规划:图状动规,树状动规,二次动规.,back,图状动规,城堡某国聪明美丽的公主要找一位如意郎君，她希望未来的夫君是一个聪明善良，节俭但又不吝啬的人。为了找到理想的人选，她的爸爸国王，给她修建了一座城堡，这个城堡有很多房间，房间之间有走廊连接，但每进入一个房间必须要花费一定数量的钱币，公主就在某个房间中等待。开始，国王给每个候选人一样多的钱币，候选人从同一个地点出发，直到找到美丽的公主为止，如果这时哪个人找到了公主，并且钱币刚好用完，那么他将会赢得公主的芳心。,back,城堡,乍看此题,似乎就是搜没得说了,是吗?如果告诉你这一题是动态规划的话,你会怎么做?状态是什么动态转移方程是什么?,back,城堡,既然是问我们能不能到达,所以想想就应该知道,动规的数组是bool型的.一开始时,只有出发的房间记为true.但是,并不是以每个房间作为状态,因为还存在一个把钱用光的问题.到达同一个房间时,如果剩余的钱不一样,也就会有不同的决策.所以状态就是在剩余j个钱币的时候能否到达第i个房间.用fi,j来表示.,back,图状动规,于是动态转移方程也就出来了,fi,j:=fi,jorfk,j+ci,K表示的是和I连接的一个房间,ci表示进入I号房间的花费.,back,树状动规,没有上司的晚会某公司要举办一次晚会，但是为了使得晚会的气氛更加活跃，每个参加晚会的人都不希望在晚会中见到他的上司，要不然他们会很扫兴。现在已知每个人的活跃指数和上司关系（当然不可能存在环），求邀请哪些人来能使得晚会的总活跃指数最大。,back,没有上司的晚会,按照要求构建一张关系图，可见这是一棵树。对于这类最值问题，向来是用动态规划求解的。任何一个点的取舍可以看作一种决策，那么状态就是在某个点取的时候或者不取的时候，以他为跟的子树能有的最大活跃总值。分别可以用fi,1和fi,0表示。,back,没有上司的晚会,当这个点取的时候，他的所有儿子都不能取，所以fi,1:=sum(fj,0,j为i的儿子)i的权值。不取的时候，他的所有儿子取不取无所谓，不过当然应该取价值最大的一种情况。所以fi,0:=sum(max(fj,1,fj,0),j为i的i儿子）。这就是树状动规的基本形态。,back,二次动规,在动规的基础上再进行动规，就叫做二次动规。买票有一座n层的楼房，某个人要到第n层的任何一个房间买票。每层楼都有m个房间。而如果要到第i层的第j个房间买票，那么必须先在第i-1层的第j个房间买票或者在第i层的与这个房间相邻的房间买过票才行.而每个房间所要收取的票费是不同的,给定每个房间内买票需要的费用,问要在第n层的任意一间房间内买到票的最小消费是多少.,back,买票,显然不能写这样的状态转移方程:fi,j:=min(fi-1,j,fi,j-1,fi,j+1)+wj.因为无法有一种处理顺序使得在fi,j之前同时求得fi,j-1和fi,j+1的最优值.所以动规分两次进行.第一次用状态转移方程fi,j:=min(fi,j-1,fi-1,j)+wi求出一个不一定是最优的解.再用fi,j:=min(fi,j,fi,j+1,jfromm-1downto1)+wi求出最终的最优解,可以证明这样的能够求出真正的最优解.要注意的是这两次动规不能分开做,而要在处理每一层的时候都要做,要不然显然无法求得最优值。,back,综合题,网络（Ural1056,求树的中心）题目大意是：有一棵有N个结点的树，给出每个结点的父亲（即给出这棵树），边的权都是1。每个结点延树的边可以走到树的任意一个结点，令Ai为第i个结点最远能走的距离，求出Ai最小的结点有哪些。如有多个最小的Ai，则都要输出。这里N=10000,back,网络,枚举每个点，然后DFS复杂度O(N2)，超时是显然的事情。可以发现其实有很多DFS都重复做了同样的工作，产生了浪费，所以应该选择动态规划解决这个问题。树上的动规，是否直接可以写出下面的状态转移方城呢？fi:=max(fson,ffather)+1废话，显然是不行的，son和father的值不可能同时得到。但是不要放弃，解决这个冲突的方法，就是采用二次动规。,back,网络,第一次动规做fi:=max(fson)+1，第二次动规做fi:=max(fi,ffather+1)。但是存在一个问题就是如果ffather的值是从i那里得到的，这样计算显然就错了。不要放弃，在实际操作过程中，f需要记下两个值，一个是最优值，一个是次优值，这两个值必须由不用的子结点得到。这样当最优值发生矛盾的时候，次优值一定不会矛盾。问题就解决了。复杂度O(N)十分的理想。,back,总结,动态规划有很多东西还需要我们更加努力地去探索和学习.总体上说来,动态规划是个既简单又不简单的算法,熟练地掌握了动态规划,也就熟练地控制了比赛.,back,Thatsall!,Thankyouforlistening.,back,动规练习题,垃圾陷阱（USACO&TJU1087）卡门农夫约翰极其珍视的一条Holsteins奶牛已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方，它的深度为D(2=D=100)英尺。卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。假设卡门预先知道了每个垃圾扔下的时间t(0t=1000)，以及每个垃圾堆放的高度h(1=h=25)和吃进该垃圾能维持生命的时间f(1=f=30)，要求出卡门最早能逃出井外的时间，假设卡门当前体内有足够持续10小时的能量，如果卡门10小时内没有进食，卡门就将饿死。,动规练习题,字符串距离（TJU1086）设有字符串X，我们称在X的头尾及中间插入任意多个空格后构成的新字符串为X的扩展串，如字符串X为“abcbcd”，则字符串“abcbcd”，“abcbcd”和“abcbcd”都是X的扩展串，这里“”代表空格字符。如果A1是字符串A的扩展串，B1是字符串B的扩展串，A1与B1具有相同的长度，那么我们定义字符串A1与B1的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的ASCII码的差的绝对值，而空格字符与其它任意字符之间的距离为已知的定值K，空格字符与空格字符的距离为O。在字符串A、B的所有扩展串中，必定存在两个等长的扩展串A1、B1，使得A1与B1之间的距离达到最小，我们将这一距离定义为字符串A、B的距离。请你写一个程序，求出字符串A、B的距离。,动规练习题,二叉苹果树（Ural1018）有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）这棵树共