动态规划入门篇.ppt

《动态规划入门篇.ppt》由会员分享，可在线阅读，更多相关《动态规划入门篇.ppt（63页珍藏版）》请在三一办公上搜索。

1、动态规划入门篇,成都大学第二期ACM暑期集训李明金2009/08/12马健鸿2010/08/11,2009-8-12,成都大学ACM暑期集训DP篇李明金,1,前言,纵观ACM届，大到每年的全球总决赛，小到TC的SRM抑或各个OJ的月赛，我们很轻易的发现一个共同的规律动态规划在其中稳稳的占据了一个重要的地位。可以说，掌握了动态规划，不一定会成为大牛，但是一只大牛，是肯定精通动态规划的。,2009-8-12,成都大学ACM暑期集训DP篇李明金,2,动态规划，和分治法一样，是通过组合子问题的解而解决整个问题的。分治算法是指将问题划分成一些独立的子问题，递归求解各子问题，然后合并子问题的解而得到原问题

2、的解。于此不同，动态规划适用于子问题不是独立的情况，也就是各子问题包含公共的子子问题。动态规划对每个子子问题只求解一次，将其结果保存在一张表中，从而避免每次遇到各个子问题时重新计算答案。动态规划通常应用于最优化问题。此类问题可能有许多种可行解。每个解都有一个值，而我们希望找到一个具有最优（最大或最小）值的解。称这样的问题为该问题的“一个”最优解（而不是“确定的”最优解），因为可能存在多个取最优解的值。总结：自从有了动态规划，这个世界变得好美妙！,2009-8-12,成都大学ACM暑期集训DP篇李明金,3,目录,0.动态规划的基本步骤1.一个例题2.什么时候需要动态规划3.最优子结构4.重叠子问

3、题5.动态规划的两个重要元素状态&状态转移方程6.备忘录介绍7.例题 数字三角形花束摆放 最大数字子串积木游戏 Subsquence 炮兵阵地(状态压缩动态规划)8.练习:NOJ 江苏省赛回放 C D E（三角形演变题）H,2009-8-12,成都大学ACM暑期集训DP篇李明金,4,0.动态规划的基本步骤,1）描述最优解的结构2）递归定义最优解的值3）按自底向上的方式计算最优解的值4）由计算出的结果构造一个最优解第1-3步构成问题的动态规划解的基础。第四步只要求计算最优解的值时可以略去。如果的确做了第四步，则有时要在第三步的计算中记录一些附加信息，使构造一个最优解变得容易。,2009-8-12

4、,成都大学ACM暑期集训DP篇李明金,5,1.一个例题,例一：装配线调度问题描述：某汽车工厂有2个装配线，每个装配线有n 个装配站（按顺序编号1n），两个装配线对应的装配站执行相同的功能，但所用的时间可能不同。经过第i条流水线（i=1，2）的第j 个装配站所花的时间为Aij。从第i条流水线的第j 个装配站移到第j+1个装配站的时间可以忽略，而移到另外一个流水线的下一个装配站则需要一定的时间Tij。汽车进入流水线不需要花时间，出流水线时需要花时间Tin。开始进入装配线i的时间是 ei。结束离开装配线i的时间是 xi。汽车的装配需要按顺序经过所有装配站。现在已知装配时间Aij 和转移时间Tij，要

5、求输出装配一辆汽车所需要的最短时间。,2009-8-12,成都大学ACM暑期集训DP篇李明金,6,方案一：暴力搜索，穷举所有装配可能，然后选择极小。显然这个方案是不可行的，因为我们分析可知，装配方式共有2N种（将所使用装配站一内的站看做一个集合，全集是1.N，子集就有2N），这时时间复杂度到达O（2N），显然N太大的时候是一定会TE的。,2009-8-12,成都大学ACM暑期集训DP篇李明金,7,方案二：动态规划。步骤一：描述最优解的结构在这里就是通过工厂最快路线的结构其实这里就是描述问题是否具有一个最优子结构，即可以利用子问题的最优解构造原问题的一个最优解。在这道题中，观察一条通过S1，j的

6、最快路线，我们发现，它必然是通过S1，j-1或S2，j-1中的一个的最快路线（如果不是最快，则自我矛盾，S1，j就不是最快了）为了解决这个问题，即寻找通过人一条装配线上的装配站J的最快路线，我们解决它的子问题，即寻找通过两条装配线上的装配站J-1的最快路线。所以，对于这个问题，我们可以求子问题的最优解，从而得到原问题的最优解。PS：状态，状态转移方程的概念将会在理脱出，后面会提到，只要找好了状态方程（加元等手段），就能轻松使用动态规划。,2009-8-12,成都大学ACM暑期集训DP篇李明金,8,步骤二：一个递归的解利用子问题的最优解来递归定义一个最优解的值。在这个问题中，我们选择在两条装备线

7、上通过装配站j的最快路线的问题作为子问题（j=1，2，3.，n）。令fij表示一个底盘从起点到装配站Si，j的最快可能时间。我们的最终目标是确定底盘通过工厂的所有路线的最快时间，记做f*。f*=min(f1n+x1,f2n+x2)下面的问题就是确定f11和f21,2009-8-12,成都大学ACM暑期集训DP篇李明金,9,显然，不管是从那条线路开始装配的，底盘肯定是直接到达装配站1的，也就是说之前是不用计算转移到装配站1的时间的。则f11=e1+a1,1 f21=e2+a2,1现在计算fij，显然简单递推可知：fi1=ei+ai,1;f1j=min(f1j-1+a1,j,f2j-1+t2,j-

8、1+a1,j)f2j=min(f2j-1+a2,j,f1j-1+t1,j-1+a2,j)fij的值就是子问题的最优解的值。注意：这里，我们不需要知道最优解到底是什么，我们只需要求出最优解是多少即可，所以对构造过程可以不进行跟踪。,2009-8-12,成都大学ACM暑期集训DP篇李明金,10,现在，写出一个递归算法计算通过工厂的最快路线是一件很简单的事情了。只需基于以下几个公式即可：f*=min(f1n+x1,f2n+x2)fi1=ei+ai,1;f1j=min(f1j-1+a1,j,f2j-1+t2,j-1+a1,j)f2j=min(f2j-1+a2,j,f1j-1+t1,j-1+a2,j)现

9、在我们来看这种算法的时间复杂度，发现它有一个问题:它的执行时间是关于n的指数形式即O（2n），这是一个时间复杂度很高的算法。我们来考虑是否能进一步提高它的效率。,2009-8-12,成都大学ACM暑期集训DP篇李明金,11,2009-8-12,成都大学ACM暑期集训DP篇李明金,12,现在考虑这样一种方式FASTEST-WAY(a,t,e,x,n)f11=e1+a1,1f21=e2+a2,1/这两行计算f11和f21的值For j=2 to n/这个循环用来计算fij的值 do if f1j-1+a1,j=f2j-1+t2,j-1+a1,j then f1j=f1j-1+a1,j else f

10、1j=f2j-1+t2,j-1+a2,j if f2j-1+a2,j=f1j-1+t1,j-1+a2,j then f2j=f2j-1+a2,j else f2j=f2j-1+ti,j-1+a2,jif f1n+x1=f2n+x2/计算f*的值 then f*=f1n+x1 else f*=f2n+x2问题，这样计算比直接递归的优势是什么？,解答：减少了重复计算，因为每次计算是试用了上次计算时得出的值，相当于在一个表格里做了记录，使得后面的再次计算时不需要重复计算。这就是后面要讲到的“备忘录”的基本思想。此题A毕总结：这是一道动态规划的典型题目，经典的由重复的子问题的最优解得到原问题的最优解。

11、,2009-8-12,成都大学ACM暑期集训DP篇李明金,13,2.什么时候需要动态规划,动态规划通常应用于最优化问题。此类问题可能有许多种可行解。每个解都有一个值，而我们希望找到一个具有最优（最大或最小）值的解。称这样的问题为该问题的“一个”最优解（而不是“确定的”最优解），因为可能存在多个取最优解的值。动态规划主要用于组合优化问题，即求一个离散问题在某种意义下的最优解，有时也用于组合计数问题。,2009-8-12,成都大学ACM暑期集训DP篇李明金,14,动态规划使用的基本条件就是：1)最优子结构性质 一个问题可用动态规划有效求解的基本要求是该问题具有最优子结构性质，通俗地讲即问题的最优解

12、包含其子问题的最优解。(2)子问题重叠性质 动态规划所针对的问题还有另外一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复，称为子问题重叠性质。在应用动态规划时，对于重复出现的子问题，只需在第一次遇到时加以求解，并把答案保存起来，以便以后再遇到时直接引用，不必重新求解，从而大大地提高解题的效率。相比之下，一般的搜索技术，对于某个子问题，不管是否已经求解过，只要遇上，就会再次对它求解，因而影响了解题的效率。,2009-8-12,成都大学ACM暑期集训DP篇李明金,15,3.最优子结构,用动态规划求最优化问题的第一步是描述最优解的结构。回顾一下，如果问题的一个最优解中包含子问题的最优解，

13、则该问题具有最优子结构。当一个问题具有最优子结构时，提示我们动态规划可能会适用（注意，在这种情况下，贪心策略可能也是适用的）在动态规划中，我们利用子问题的最优解来构造问题的一个最优解。因此，必须小心以确保在我们所考虑的子问题的范围中，包含了用于一个最优解中的那些子问题。在前面的装配线的例子中，可以看到在任何一条装配线上，通过装配站j的最快路线包含了在其中一条装配线上通过装配站j-1的最快路线。,2009-8-12,成都大学ACM暑期集训DP篇李明金,16,在寻找最优子结构时，可以遵循一种共同的模式：1）问题的一个解可以是做一个选择。例如，选择一个前一个装配线装配站。做这种选择会得到一个可以导致

14、最优解的选择。2）假设对一个给定的问题，已知的是一个可以导致最优解的选择。不必关心如何确定这个选择，尽管假定它是已知的。3）在已知这个选择后，要确定哪些子问题会随之发生，以及如何最好的描述所得到的子问题空间4）利用一种“剪贴”技术，来证明在问题的一个最优解中，使用的子问题的本身必须也是最优的，通过假设每一个子问题的解都不是最优解，然后导出矛盾，即可做到这一点。如果有多于一个子问题的话，由于他们通常非常类似，所以只要对其中一个子问题的“剪贴”稍加修饰，计科很容易的用于其它子问题。,2009-8-12,成都大学ACM暑期集训DP篇李明金,17,为了描述子问题空间，可以遵循这样一条有效的经验规则，就

15、是尽量保持这个空间简单，然后在需要的时候再扩充它。例如，在装配线问题中，我们所考虑的子问题空间（其实就是后面要讲的“状态方程”）就是从工厂入口通过装配站S1，j和S2，j的最快路线。这个子问题空间很合适，因为没必要研究其他。但是往往在很多问题中，这个空间不是这么明显的，这个时候，就需要扩展子问题，得到合适的子问题空间（在后面的数字三角形中会出现这种情况，请大家注意）,2009-8-12,成都大学ACM暑期集训DP篇李明金,18,最优子结构在问题域中以两种方式变化：1）有多少个子问题被使用在与原问题的一个最优解中2）在决定一个最优解中使用哪些子问题时有多少个选择。在装配线调度问题中，一个最优解只

16、使用了一个子问题，但是，为确定一个最优解，我们必须考虑两种选择。为找出通过装配站Sij的最快路线，我们使用通过S1，j-1或S2，j-1的最快路线；不管采用了哪一种，它都代表了必须最优解决的子问题。,2009-8-12,成都大学ACM暑期集训DP篇李明金,19,非正式的，一个动态规划算法的运行时间依赖于两个因素的成绩：子问题的总个数和没一个子问题中有多少种选择。在装配线调度中，总共有O（n）个子问题，并且只有两个选择来检查每个子问题，所以执行时间为O（n）。动态规划是采用自底向上的方式利用最优子结构。也就是说，首先找到子问题的最优解，解决子问题，然后找到问题的一个最优解。寻找问题的一个最优解需

17、要在子问题中做出选择，即选择将用哪一个来求解问题。,2009-8-12,成都大学ACM暑期集训DP篇李明金,20,4.重叠子问题,适用于动态规划求解的最优子问题必须具有的第二个要素是空间要“很小”，也就是用来解决原问题的递归算法可反复地解同样的子问题。当一个递归算法不断调用同一个问题时，我们说该最优问题包含重叠子问题针对动态规划产生大量重叠子问题的情况，提出了两种方案，一是：记忆化搜索（即本PPT的第6部分内容备忘录）；二是：自底向上的递推（前面的装配线问题，我们就是用这种方式改进的算法效率）。,2009-8-12,成都大学ACM暑期集训DP篇李明金,21,5.状态&状态转移方程,我们从前面的

18、例题中不难感觉到，完成动态规划算法的一个关键点就是写出递推式和边界条件。那么，我们把所选出的状态记为d，d值的递推式即被称为状态转移方程。这样，就很容易写出一个三重循环，第一层按一定的顺序计算每个状态，第二层在计算每个状态时考虑不同的递推路径（称为决策数目），最里层进行每个单独状态转移。算法复杂度=状态数*决策数目*转移费用。状态是一个很重要的概念，如果算法基础过关，那么，成功的为一个题目设计出状态的时候，动态规划已经完成了一大半。设计状态的时候，需要考察问题的无后效性，然后思考状态转移的时候需要考察问题的最优子结构。,2009-8-12,成都大学ACM暑期集训DP篇李明金,22,无后效性：就

19、是说，只有这个决定了今后的决策，即：决策只取决于当前状态的特征因素，而与到达此状态的方式无关，我们把这种性质就叫做无后效性。问题表示与状态定义的区别：有了问题的表示之后，状态的含义不一定确定下来了向前递推法和向后递推法增加维数获得无后效性的状态表示。状态转移的可定义性来自问题的最优子结构。,2009-8-12,成都大学ACM暑期集训DP篇李明金,23,6.备忘录介绍,备忘录（memoization，这并不是拼写错误，这个单词确实是memoization，而不是memorization memraizein。memoization 来源于memo memu，因为这个方法主要是记录一个值，以便以后

20、可以搜索它。）,2009-8-12,成都大学ACM暑期集训DP篇李明金,24,动态规划的另外一种变形，它既有通常的动态规划的效率，又采用了一种自顶向下的策略。其思想就是备忘（memoize）原问题的自然但低效的递归算法。想在通常的动态规划中一样，维护一个子问题解的表，但有关填表动作的控制结构更像递归算法。加了备忘的递归算法为没一个子问题的解在表中记录一个表项。开始时，每个表项最初都包含一个特殊值，以表示该表项有待填入。当在递归算法的执行中第一次遇到一个子问题时，就计算它的解并填入表中。以后每次遇到该子问题的时候，只要查看并且并且返回表中先前填入的值即可。备忘录的具体在算法中的实现，这里就不在赘

21、述，有兴趣的同学可以在理解了后面的例题的情况下，将它们改写成用备忘录实现的DP。,2009-8-12,成都大学ACM暑期集训DP篇李明金,25,7.例题,例一：数字三角形问题描述 给定一个具有N层的数字三角形，从顶至底有多条路径，每一步可沿左斜线向下或沿右斜线向下，路径所经过的数字之和为路径得分，请求出最小路径得分。2 6 2 1 8 4 1 5 6 8图11 数字三角形,2009-8-12,成都大学ACM暑期集训DP篇李明金,26,解题思路 这道题可以用动态规划成功地解决，但是，如果对问题的最优结构刻画得不恰当(即状态表示不合适)，则无法使用动态规划。状态表示法一：用一元组D(X)描述问题，

22、D(X)表示从顶层到达第X层的最小路径得分。因此，此问题就是求出D(N)(若需要，还应求出最优路径)。这是一种很自然的想法和表示方法。遗憾的是，这种描述方式并不能满足最优子结构性质。因为D(X)的最优解(即最优路径)可能不包含子问题例如D(X-1)的最优解。如图11所示：,2009-8-12,成都大学ACM暑期集训DP篇李明金,27,如图,2009-8-12,成都大学ACM暑期集训DP篇李明金,28,显然，D(4)2+6+1+110，其最优解(路径)为2-6-1-1。而D(3)2+2+48，最优解(路径)为2-2-4。故D(4)的最优解不包含子问题D(3)的最优解。由于不满足最优子结构性质，因

23、而无法建立子问题最优值之间的递归关系，也即无法使用动态规划。,2 6 2 1 8 4 1 5 6 8图11 数字三角形,状态表示法二：用二元组D(X,y)描述问题，D(X,y)表示从顶层到达第X层第y个位置的最小路径得分。最优子结构性质：容易看出，D(X,y)的最优路径Path(X,y)一定包含子问题D(X-1,y)或D(X-1,y-1)的最优路径。否则，取D(X-1,y)和D(X-l,y-1)的最优路径中得分小的那条路径加上第X层第y个位置构成的路径得分必然小于Path(X,y)的得分，这与Path(X,y)的最优性是矛盾的。因为每次只能向左下或右下走，所以，一旦D（x，y）确定了，那么显然

24、，下一步的时候，只跟现在这个位置有关，不关心前面是怎么过来的，这也就满足了无后效性。,2009-8-12,成都大学ACM暑期集训DP篇李明金,29,如图,2009-8-12,成都大学ACM暑期集训DP篇李明金,30,2 6 2 1 8 4 1 5 6 8图11 数字三角形,如图11所示，D(4,2)的最优路径为2-6-1-5，它包含D(3,1)最优路径2-6-1。因此，用二元组D(X,y)描述的计算D(X,y)的问题具有最优子结构性质。,递归关系：D(X,y)minD(X-1,y)，D(X-1,y-1+a(X,y)D(1,1)a(1,1),其中，a(X,y)为第X层第y个位置的数值。原问题的最

25、小路径得分可以通过比较D(N,i)获得，其中i1，2，N。在上述递归关系中，求D(X,y)的时候，先计算D(X-1,y)和D(X-1,y-1)，下一步求D(X，y+1)时需要D(X-1，y+1)和D(X-1，y)，但其中D(X-1，y)在前面已经计算过了。于是，子问题重叠性质成立。因此，采用状态表示法二描述的问题具备了用动态规划求解的基本要素，可以用动态规划进行求解。,状态表示法三：采用状态表示法二的方法是从顶层开始，逐步向下至底层来求出原问题的解。事实上，还可以从相反的方向考虑。仍用二元组D(X,y)描述问题，D(X,y)表示从第X层第y个位置到达底层的最小路径得分。原问题的最小路径得分即为

26、D(1,1)。最优子结构性质：显然，D(X,y)的最优路径Path(X,y)一定包含子问题D(X+1,y)或D(X+1,y+1)的最优路径，否则，取D(X+1,y)和D(X+1,y+1)的最优路径中得分小的那条路径加上第X层第y个位置构成的路径得分必然小于Path(X,y)的得分，这与Path(X,y)的最优性矛盾。,2 6 2 1 8 4 1 5 6 8图11 数字三角形,如图所示，D(1，1)的最优路径为2-6-1-1，它包含D(2,1)的最优路径6-1-1。因此，这种状态表示描述的计算D(X，y)的问题同样具有最优子结构性质。,递归关系：D(X,y)minD(X+1,y),D(X+1,y

27、+1)+a(X,y)D(N,k)a(N,k)，k1，N,其中，a(X，y)为第X层第y个位置的数值。D(X,y)表示从第X层第y个位置到达底层的最小路径得分。原问题的最小路径得分即为D(1,1)。,算法设计 采用状态表示法三的算法的主要过程如下：for(i=n-2;i=0;-i)/从最下层开始，计算每个x，y位/置的元素到 最后一行的最小值for(j=0;j=i;+j)/计算每一行的每一个数字tmp=soui+1j;if(soui+1j+1 tmp)/*j在变化，j每循环完次都得到一个这一行到最底行最小的位置，同时也记录了每个位置到最底行的值；这里的if是在找每个位置的下两步路线中较小的一个*

28、/tmp=soui+1j+1;souij+=tmp;printf(%dn,sou00);,例题二：花束摆放问题描述 现在有F束不同品种的花束，同时有至少同样数量的花瓶被按顺序摆成一行，其位置固定于架子上，并从1至V按从左到右顺序编号，V是花瓶的数目(FV)。花束可以移动，并且每束花用1至F的整数唯一标识。标识花束的整数决定了花束在花瓶中排列的顺序，如果ij，花束i必须放在花束j左边的花瓶中。每个花瓶只能放一束花。如果花瓶的数目大于花束的数目，则多余的花瓶空置。,2009-8-12,成都大学ACM暑期集训DP篇李明金,36,每一个花瓶都具有各自的特点。因此，当各个花瓶中放入不同的花束时，会产生不

29、同的美学效果，并以一美学值(一个整数)来表示，空置花瓶的美学值为零。为取得最佳美学效果，必须在保持花束顺序的前提下，使花束的摆放取得最大的美学值。请求出具有最大美学值的一种摆放方式。,2解题思路 状态表示法一：设A(i,j)表示第i种花束摆在第j个花瓶中获得的美学值。S(i,k)表示第i种花束摆在第k个花瓶中时(这里ki)，前i种花束能够获得的最大美学值(之和)。这样，原问题的最优值可以通过计算maxS(F,k)FkV获得。下面要分析一下这种状态表示法描述问题的方式是否具备了用动态规划求解的基本要素。,最优子结构性质：对满足FkV的k，设T(F,k)是达到最优值S(F,k)的一种最佳摆放方式，

30、其中，第F-1种花束摆在第j个花瓶中(j1每走一步，计算出了所有i的花束摆放在所有可能的位置之后的所有值。最后，递推出了s(F,*)的值取最大既得到结果。S(1,k)=A(1,k)第i-1个花摆在那里之后，下一步怎么摆，只跟现在花在哪里有关，而与前面的摆放顺序无关，无后效性。大家用心想一下，问题其实还是像装配线一样，被分解成了有限个分支的最大值问题。切记，使用DP的时候，眼光不要一直盯着最后的最优，一步一步看，只要你现在最优，并且无后效性，就可以DP下去。,在计算S(i,k-1)时，已经计算出了S(i-1,j)，i-1jk-2及其 maxS(i-1,j)i-1jk-2。因此，计算S(i,k)时

31、，只要将S(i-1,k-1)与max S(i-1,j)i-1jk-2 进行比较即可求得,即子问题重叠性质。这样做可以大大减少计算量。即不用每次都去全部比较，求最大值。事实上，还可以有更直接的方法。状态表示法二：设Si,k表示第i种花束摆在第k个之前(包括第k个)的任意某个花瓶中，前i种花束能够获得的最大美学值(之和)。这样，原问题的最优值即为SF,V。这比前一个表示法更直接。,容易验证，计算SF,V的问题具有最优子结构性质。其递归方程为：Si,k=maxSi-1,k-1+A(i,k)，Si,k-1，(i1，ki);/很精妙，注意理解 初始条件为：S1,1=A1,1;S1,k=maxA(1,k)

32、,S1,k-1，(k1);Si,i=Si-1,i-1+A(i,i)，(i1),算法设计(状态表示法二)算法的过程如下：s00=a00;out00=true;for(j=1;j a0j?s0j-1:a0j;out0j=(s0j!=s0j-1);for(i=1;i?=si-1j-1+aij;outij=(sij!=sij-1);,sij=si-1j-1+aij;outij=true;if(i?=sij-1;outij=(sij!=sij-1);,Hdu 1087 Super Jumping!Jumping!Jumping!,求最大和上升子序列Sample Input3 1 3 2 4 1 2 3

33、4 4 3 3 2 1 0Sample Output4 103,int main()int n,i,j,max,sum;while(cinn,n)int*a=new intn;int*b=new intn;for(i=0;iai;b0=a0;,for(i=1;iaj,Hdu 1003 Max Sum,求最大连续和,25 6-1 5 4-77 0 6-1 1-6 7-5Sample OutputCase 1:14 1 4Case 2:7 1 6,int main()int max,sum,num,start,end,temp;int t,n;cin t;for(int j=1;j n;max=-

34、1001,sum=0,temp=1;for(int i=1;i num;sum=sum+num;if(sum=max)max=sum;start=temp;end=i;if,if(sum 0)sum=0;temp=i+1;cout Case j:endl;cout max start end endl;if(j!=t)cout endl;return 0;,例题三：最大数字子串NKOJ 1760 最大数字子串:问题描述：输入n(1=n=1e6)和n个整数，这n个整数的绝对值均小于1000，求最大数字子串之和。Sample Input 9-3 4 9 2-10-7 11 3-8 13-1 2 6

35、-3 5-7 14-5-15 1 8-4 9Sample Output 15 17 Hint 在第一组中，最大的数字子串是4 9 2的和在第二组中，最大的数字子串是2 6-3 5-7 14的和-3 4 9 2-10-7 11 3-8-1 2 6-3 5-7 14-5-15 1 8-4 9,2009-8-12,成都大学ACM暑期集训DP篇李明金,46,显然可以在数串读入以后用搜索的方法找出这个最大子串！也很显然那样很麻烦！怎么办呢？考虑每输入一个数的时候便做记录，那样等数串读入完毕的时候，最大子串和到底是多少也就知道了！这算动态规划的一个引申!,以第一例为例：,-3 4 9 2-10-7 11

36、3-8记录方法：-3 4 13 15 5-7 11 14 6 把当前的最大和（含当前末尾的最大和）记录下来，虽然不能直接得出最大和是多少，但可以进行遍历搜索最大值即可！,关键是要对负数处理好，看例二，最大子串含有负数。-1 2 6-3 5-7 14-5-15 1 8-4 9-1 2 8？如果在此处断开记录-3，那么前面的2，6 两个正数就和后边断开了，实际上2+6+（-3）0，如果后边是正数的话，完全可以加上这3个数（比如后边的5）-1 2 8 5 10？相同处理：-1 2 8 5 10 3 17 12？后面是-15，加上12（前面的子串能形成的最大和）也小于0，所以此处应该断开了！记录-15

37、！最后-1 2 8 5 10 3 17 12-15 1 9 5 14,！,还有一点，如果输入全为非正数的话，那么最大子串就是最大的那个数了！,伪代码：,输入数组ai,用数组si记录当前最大子串和,num记录最大值。for(i=0;in;i+)输入ai;s0=a0;num记录当前最大的数；if(num=0)最大就为num!for(i=1;in;i+)if(si-1 0|(si-1+ai)=0)si=ai;elsesi=si-1+ai;num=(num si)?si:num;/*条件运算符（numbi true则bi,false则num）*/,例题四：积木游戏LRJ的书，P119。这道题和我们程序

38、设计大赛的时候的第四题（是不是第四？记不清了。）猩猩吃香蕉那题有异曲同工之妙。大家明白这题之后可以回忆一下我们的比赛。,2009-8-12,成都大学ACM暑期集训DP篇李明金,52,例题五：Subsquence 给定一个数串和一个数S，在数串中找出大于等于S的一个连续子列！且该子列是满足上述条件的最短子列！数串数字个数N：10N100000,每个数小于10000。比如：10 15 5 1 3 5 10 7 4 9 2 8 最短为2；5 11 1 2 3 4 5 最短为3。,2009-8-12,成都大学ACM暑期集训DP篇李明金,53,该题简单分析：,题意知所有数全为正数 A sequence

39、of N positive integers(10 N 100 000)，每新增一个数，若前面的数不足S,加上此数，然后与S比较！小于S可不管！,大于S：假设此时新增项ai,设当前和为sumi,用另一数组记录当前长度位置长度lengthi。那么现在在构成sumi的数的最前端i-lengthi+1处，有可能出现多余的项，哪怕删除它们也满足剩下的数的和sumi(长度已更改为新的lengthi!)逐项除之即可！lengthi记录的是到达每个位置的时候，这个串现在有多长。,寻找最短子列：,Length全为0,没有最短子列!否则为大于0的最小值。if(b1n-1=0)num=0;else num=n;f

40、or(i=0;i0)num=(b1inum)?b1i:num;,例题六：炮兵阵地POJ 1185经典的DP问题题意描述：司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用H 表示），也可能是平原（用P表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：,2009-8-12,成都大学ACM暑期集训DP篇李明金,57,如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上

41、其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。,2009-8-12,成都大学ACM暑期集训DP篇李明金,58,Input第一行包含两个由空格分割开的正整数，分别表示N和M；接下来的N行，每一行含有连续的M个字符(P或者H)，中间没有空格。按顺序表示地图中每一行的数据。N=100；M=10。Output仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。Sample Input5 4

42、 PHPP PPHH PPPP PHPP PHHP Sample Output6,2009-8-12,成都大学ACM暑期集训DP篇李明金,59,这道题给大家留做思考题，大家可以先考虑一下，这道题的状态方程该怎么描述，试着A一下，但是这个题直接DP是A不过的，因为不论是时间还是空间都会超，这道题还有一个关键点，就是状态压缩，今天我们已经讲了很多内容了，所以状态压缩的DP今天就不讲了，我会在下次的动态规划提高篇中详细讲解这道题。,2009-8-12,成都大学ACM暑期集训DP篇李明金,60,OK，今天的课程和题目到这里就完成了，今天的内容很多，但是，还远远达不到对DP的哪怕沧海一粟般的描述，而且，DP是ACM中的重中之重，所以大家下课之后，一定回去将概念和例题多读多看，对概念要理解并掌握，对例题要能熟练的一眼就写出状态方程。最后，留下几道练习题，大家可以在看熟了课件并掌握了例题之后来试试身手。地址是：http:/=contestDetail&contestId=15其中的C D E（三角形演变题）H 四道题，题目不多，是江苏省赛的回放中的几道题，大家试下身手。,2009-8-12,成都大学ACM暑期集训DP篇李明金,61,谢谢,2009-8-12,成都大学ACM暑期集训DP篇李明金,62,再谢一下这下结束了O(_)O,2009-8-12,成都大学ACM暑期集训DP篇李明金,63,