[计算机]DP-坐标规则型动态规划ppt课件

1、坐标规那么型动态规坐标规那么型动态规划划Robots 在一个在一个n*m的棋盘内，一些格子里有垃圾要的棋盘内，一些格子里有垃圾要拾捡。如今有一个能捡垃圾的机器人从左拾捡。如今有一个能捡垃圾的机器人从左上格子里出发，每次只能向右或者向下走。上格子里出发，每次只能向右或者向下走。每次他到达一个点，就会自动把这个点内每次他到达一个点，就会自动把这个点内的垃圾拾掉。的垃圾拾掉。 问：最多能拾多少垃圾。在最多的情况下，问：最多能拾多少垃圾。在最多的情况下，有多少种拾垃圾方案？有多少种拾垃圾方案？ 数据范围数据范围:n=100,m=100样例分析 最多能拾最多能拾5块。有块。有4种方法。种方法。分析1 因

2、为机器人只能向右或者向下走。符合无因为机器人只能向右或者向下走。符合无后效性原那么。于是考虑动态规划。后效性原那么。于是考虑动态规划。 设设Fi,j表示从表示从1,1点开场走到点开场走到i,j的时候，最多捡了多少垃圾。的时候，最多捡了多少垃圾。 Fi,j=Maxfi-1,j,fi,j-1+ci,j 其中其中Ci,j=1表示表示i,j点有垃圾。点有垃圾。Ci,j=0表示没有表示没有 1=i=n,1=j=m，决策，决策2种种 时间复杂度为时间复杂度为On*m分析2 设设Gi,j表示在表示在fi,j最大的时候，有多少种方最大的时候，有多少种方案。案。 捡到捡到fi,j的垃圾只能从两个方向来走，的垃圾

3、只能从两个方向来走，方案数累加即可。因此，方案数累加即可。因此，gi,j=gi-1,j*k+gi,j-1*L假如假如fi-1,j+ci,j=fi,j，那么，那么K=1否那么否那么K=0。假如假如fi,j-1+ci,j=fi,j，那么，那么L=1否那么否那么L=0 时间复杂度时间复杂度On*m 矩阵取数游戏矩阵取数游戏 NOIP2007 对于一个给定的对于一个给定的n*m的矩阵，矩阵中的每个元素的矩阵，矩阵中的每个元素aij为非负整数。游戏规那么如下：为非负整数。游戏规那么如下：1. 每次取数时须从每行各取走一个元素，共每次取数时须从每行各取走一个元素，共n个。个。 m次次后取完矩阵所有的元素；

4、后取完矩阵所有的元素；2. 每次取走的各个元素只能是该元素所在行的行首或行每次取走的各个元素只能是该元素所在行的行首或行尾；尾；3. 每次取数都有一个得分值，为每行取数的得分之和；每次取数都有一个得分值，为每行取数的得分之和；每行取数的得分每行取数的得分 = 被取走的元素值被取走的元素值* *2i，其中，其中i表示第表示第i次取数从次取数从1开场编号；开场编号；4. 游戏完毕总得分为游戏完毕总得分为m次取数得分之和。次取数得分之和。 求出取数后的最大得分。求出取数后的最大得分。样例 输入输入 2 31 2 33 4 2 输出输出82 第第1次：第一行取行首元素，第二行取行尾元素，次：第一行取行

5、首元素，第二行取行尾元素，本次的气氛本次的气氛1*21+2*21=6 第第2次：两行均取行首元素，本次得分为次：两行均取行首元素，本次得分为2*22+3*22=20 第第3次：得分为次：得分为3*23+4*23=56。总得分为。总得分为6+20+56=82数据范围 60%的数据满足：1=n, m=30，答案不超过1016 100%的数据满足：1=n, m=80，0=aij=1000 1*21+2*21=6 2*22+3*22=20 3*23+4*23=561*21+2*22+3*23= 2*21+3*22+4*23分析分析 首先，首先，n行求值可以独立考虑！行求值可以独立考虑！ 设设fi,j表

6、示区间表示区间i-j的最优值的最优值 fi,j=maxfi+1,j+w*ai , fi,j-1+w*aj 其中其中w=w+w,即即w*2 需要做假设干次高精度加法和乘法。需要做假设干次高精度加法和乘法。 直到求出，直到求出，maxfi,i+w*ai，i=1.m为止。为止。传纸条传纸条NOIP2020 小渊坐在矩阵的左上角，坐标小渊坐在矩阵的左上角，坐标1,1，小轩坐在矩阵的，小轩坐在矩阵的右下角，坐标右下角，坐标m,n。从小渊传到小轩的纸条只可以向。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。向左传递

7、。 班里每个同学都可以帮他们传递，但只会帮他们一次。班里每个同学都可以帮他们传递，但只会帮他们一次。 每个同学愿意帮助的好感度有高有低，可以用一个每个同学愿意帮助的好感度有高有低，可以用一个0-100的自然数来表示，数越大表示越好心。的自然数来表示，数越大表示越好心。 小渊和小轩希望尽可能找好心程度高的同学来帮助传纸条小渊和小轩希望尽可能找好心程度高的同学来帮助传纸条，即找到来回两条传递途径，使得这两条途径上同学的好，即找到来回两条传递途径，使得这两条途径上同学的好心程度只和最大。如今，请你帮助小渊和小轩找到这样的心程度只和最大。如今，请你帮助小渊和小轩找到这样的两条途径。两条途径。 1=m,

8、n=50贪心 很容易想到一个算法：很容易想到一个算法： 求出求出1个纸条从个纸条从1，1到到M,N的道路最大值的道路最大值. 删除途径上的点值删除途径上的点值 再求出再求出1个纸条从个纸条从M,N 到到1，1的道路最大值的道路最大值. 统计两次和统计两次和 上述算法很容易找出反例，如以下图。上述算法很容易找出反例，如以下图。 第第1次找最优值传递后，导致第次找最优值传递后，导致第2次无法传递。次无法传递。分析 贪心算法错误，因此我们需要同时考虑两个纸条的传递。贪心算法错误，因此我们需要同时考虑两个纸条的传递。 由于由于小渊小渊和小轩的途径可逆，因此，尽管出发点不同，但和小轩的途径可逆，因此，尽

9、管出发点不同，但都可以看成同时从都可以看成同时从1,1出发到达出发到达M,N点。点。 设设fi1,j1,i2,j2表示纸条表示纸条1到达到达i1,j1位置，纸条位置，纸条2到达到达i2,j2位置的最优值。那么有，位置的最优值。那么有， 其中其中 i1,j1 i2,j2 1=i1, i2=M, 1=j1 , j2=N 时间复杂度时间复杂度ON2M2,) 1, 1,() 1, 1(), 1, 1,(), 1, 1(max),(221122112211221122112211jiCjiCjijifjijifjijifjijifjijif分析2 另一种思路：每个纸条都需要走另一种思路：每个纸条都需要走

10、M+N步才能到达目的。步才能到达目的。 因此，设因此，设Fk,i1,i2表示两个纸条都走了表示两个纸条都走了K步，第步，第1个纸条个纸条横坐标为横坐标为i1,第第2个纸条横坐标为个纸条横坐标为i2的最优值。的最优值。 那么两个纸条的纵坐标分别为那么两个纸条的纵坐标分别为j1=K-i1, j2=K-i2 ,状态转移方状态转移方程如下：程如下： 其中其中 i1i2 1=i1, i2=M,1=k=N+M 时间复杂度时间复杂度ON+M*M2,) 1, 1, 1() 1, 1(), 1, 1(), 1(max),(22112121212121ikiCikiCiikfiikfiikfiikfiikf免费馅

11、饼免费馅饼 SERKOISERKOI最新推出了一种叫做最新推出了一种叫做“免费馅饼免费馅饼的游戏。的游戏。 游戏在一个舞台上进展。舞台的宽度为游戏在一个舞台上进展。舞台的宽度为W W格，天幕的高度格，天幕的高度为为H H格，游戏者占一格。开场时，游戏者站在舞台的正中格，游戏者占一格。开场时，游戏者站在舞台的正中央，手里拿着一个托盘。央，手里拿着一个托盘。 游戏开场后，从舞台天幕顶端的格子中不断出现馅饼并游戏开场后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右挪动去接馅饼。游戏者每秒可以垂直下落。游戏者左右挪动去接馅饼。游戏者每秒可以向左或右挪动一格或两格，也可以站在愿地不动。向左或

12、右挪动一格或两格，也可以站在愿地不动。 馅饼有很多种，游戏者事先根据自己的口味，对各种馅馅饼有很多种，游戏者事先根据自己的口味，对各种馅饼依次打了分。同时在饼依次打了分。同时在8-3088-308电脑的遥控下，各种馅饼下电脑的遥控下，各种馅饼下落的速度也是不一样的，下落速度以格落的速度也是不一样的，下落速度以格/ /秒为单位。当馅秒为单位。当馅饼在某一秒末恰好到达游戏者所在的格子中，游戏者就饼在某一秒末恰好到达游戏者所在的格子中，游戏者就搜集到了这块馅饼。搜集到了这块馅饼。 写一个程序，帮助我们的游戏者搜集馅饼，使得搜集的写一个程序，帮助我们的游戏者搜集馅饼，使得搜集的馅饼的分数之和最大。馅饼

13、的分数之和最大。 输入数据：输入数据：第一行第一行:宽度宽度W199奇数和高度奇数和高度H1 100整数整数接下来给出了一块馅饼信息。由接下来给出了一块馅饼信息。由4个正整数组成，分别表个正整数组成，分别表示了馅饼的示了馅饼的初始下落时刻、程度位置、下落速度、分值。初始下落时刻、程度位置、下落速度、分值。游戏开场时刻为游戏开场时刻为0。从。从1开场自左向右依次对程度方向的每开场自左向右依次对程度方向的每格编号。格编号。 输出数据：输出数据：搜集到的馅饼最大分数之和。搜集到的馅饼最大分数之和。 由上图可知，尽管下落了由上图可知，尽管下落了4个馅饼，但只能接到个馅饼，但只能接到3个个： 第第1时刻

14、可以接到分值为时刻可以接到分值为5的馅饼的馅饼 第第2时刻可以接到分值为时刻可以接到分值为3的馅饼的馅饼 第第3时刻可以接到分值为时刻可以接到分值为4的馅饼的馅饼 因此馅饼的总分值为因此馅饼的总分值为5+3+4=12分析 由于馅饼下落的时间和速度都不同，人只能向左右挪动，由于馅饼下落的时间和速度都不同，人只能向左右挪动，馅饼只能向下挪动。人和馅饼都同时挪动，考虑起来比较馅饼只能向下挪动。人和馅饼都同时挪动，考虑起来比较复杂，因此我们需要转变思路：复杂，因此我们需要转变思路：算出每个时刻落到最底算出每个时刻落到最底层的每个格子有多少分层的每个格子有多少分值的馅饼。值的馅饼。假如将馅饼当成参照物，

15、假如将馅饼当成参照物，那么馅饼向下落，可以那么馅饼向下落，可以看成馅饼不动，人往上看成馅饼不动，人往上走去摘取馅饼，这样人走去摘取馅饼，这样人每每1时刻都可以走到上时刻都可以走到上一行的一行的5个格子，如右个格子，如右图：图：动态规划动态规划 计算出每个格子每个时刻可能到达的馅饼分值，填入计算出每个格子每个时刻可能到达的馅饼分值，填入W*H的天幕表。的天幕表。 其中其中Ci,j表示天幕的第表示天幕的第i行第行第j列的馅饼分值，即第列的馅饼分值，即第i时时刻，馅饼落到最底行的馅饼分值。刻，馅饼落到最底行的馅饼分值。 设设Fi,j表示人走到第表示人走到第i行行j列所获得的馅饼最大分值列所获得的馅饼

16、最大分值和，那么有，和，那么有， 0=i=T,1=j=W,决策数为决策数为5个个 时间复杂度为时间复杂度为O5WT,)2, 1() 1, 1(), 1() 1, 1()2, 1(max),(jicjifjifjifjifjifjif三角蛋糕三角蛋糕 一块边长为一块边长为n的正三角形的大蛋糕，一些被老鼠的正三角形的大蛋糕，一些被老鼠咬坏了，如以下图黑色部分。咬坏了，如以下图黑色部分。 现想把该蛋糕切出一块最大的没被老鼠咬坏正三现想把该蛋糕切出一块最大的没被老鼠咬坏正三角形的蛋糕；角形的蛋糕； 求切出的最大的三角形面积求切出的最大的三角形面积 n100。向上的三角形，向上的三角形， 设顶点坐标为设

17、顶点坐标为i,j的三角形最大高度为的三角形最大高度为Fi,j 显然：显然： Fi,j=MINFi-1,j-1,Fi-1,j+1 +1， 当当Ci-1,j=-，表示这个三角形没被老鼠咬坏。，表示这个三角形没被老鼠咬坏。向下的三角形 设顶点坐标为设顶点坐标为i,j的三角形最大高度为的三角形最大高度为Gi,j 显然：显然： Gi,j=MINGi+1,j-1,Gi+1,j+1 +1， 当当Ci+1,j=-，表示这个三角形没被老鼠咬坏。，表示这个三角形没被老鼠咬坏。分析 分别求分别求Fi,j和和Gi,j 1=i=n,1=j=2n-1 因此，时间复杂度因此，时间复杂度ON2 答案为高度的平方，证明如下：答

18、案为高度的平方，证明如下： 假设最大高度为假设最大高度为W 那么三角形个数为那么三角形个数为+2W-1=W2主程序for i:=1 to n do倒三角情况倒三角情况 for j:=i to 2*n-i do if ci,j=-andi mod 2=j mod 2 then假如该位置没被吃，而且必假如该位置没被吃，而且必须是头朝下的三角须是头朝下的三角 begin if ci-1,j- then fi,j:=1 else fi,j:=minfi-1,j-1,fi-1,j+1+1;是否可以从上面的位置转移过来是否可以从上面的位置转移过来堆成更大的三角形堆成更大的三角形 if fi,jans then ans:=fi,j; end;正三角情况程序与上类似正三角情况程序与上类似总结总结 规那么类动态规划有一个共性，那就是在