NOI导刊 坐标规则型动态规划.ppt

1、坐标规则型动态规划,长沙市雅礼中学 朱全民,Robots,在一个n*m的棋盘内，一些格子里有垃圾要拾捡。现在有一个能捡垃圾的机器人从左上格子里出发，每次只能向右或者向下走。每次他到达一个点，就会自动把这个点内的垃圾拾掉。 问：最多能拾多少垃圾。在最多的情况下，有多少种拾垃圾方案？ 数据范围:n=100,m=100,样例分析,最多能拾5块。有4种方法。,分析(1),因为机器人只能向右或者向下走。符合无后效性原则。于是考虑动态规划。 设F(i,j)表示从(1,1)点开始走到(i,j)的时候，最多捡了多少垃圾。 F(i,j)=Maxf(i-1,j),f(i,j-1)+ci,j 其中Ci,j=1表示(

2、i,j)点有垃圾。Ci,j=0表示没有 1=i=n,1=j=m，决策2种 时间复杂度为O(n*m),分析(2),设Gi,j表示在fi,j最大的时候，有多少种方案。 捡到f(i,j)的垃圾只能从两个方向来走，方案数累加即可。因此， g(i,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 时间复杂度O(n*m),矩阵取数游戏 （NOIP2007）,对于一个给定的n*m的矩阵，矩阵中的每个元素aij为非负整数。游戏规则如下： 1. 每次取数时须从每行各取走一个元素，共n个。 m次后取完矩阵

3、所有的元素； 2. 每次取走的各个元素只能是该元素所在行的行首或行尾； 3. 每次取数都有一个得分值，为每行取数的得分之和；每行取数的得分 = 被取走的元素值*2i，其中i表示第i次取数（从1开始编号）； 4. 游戏结束总得分为m次取数得分之和。 求出取数后的最大得分。,样例,输入 2 31 2 33 4 2 输出 82 第1次：第一行取行首元素，第二行取行尾元素，本次的氛围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

4、 100%的数据满足：1=n, m=80，0=aij=1000 1*21+2*21=6 2*22+3*22=20 3*23+4*23=56 1*21+2*22+3*23= 2*21+3*22+4*23,分析,首先，n行求值可以独立考虑！ 设fi,j表示区间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为止。,传纸条(NOIP2008),小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小

5、轩传给小渊的纸条只可以向上或者向左传递。 班里每个同学都可以帮他们传递，但只会帮他们一次。 每个同学愿意帮忙的好感度有高有低，可以用一个0-100的自然数来表示，数越大表示越好心。 小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度只和最大。现在，请你帮助小渊和小轩找到这样的两条路径。 1=m,n=50,贪心,很容易想到一个算法： 求出1个纸条从（1，1）到（M,N）的路线最大值. 删除路径上的点值 再求出1个纸条从（M,N） 到（1，1）的路线最大值. 统计两次和 上述算法很容易找出反例，如下图。 第1次找最优值传递后，导致第2次无法传

6、递。,分析,贪心算法错误，因此我们需要同时考虑两个纸条的传递。 由于小渊和小轩的路径可逆，因此，尽管出发点不同，但都可以看成同时从(1,1)出发到达(M,N)点。 设f(i1,j1,i2,j2)表示纸条1到达(i1,j1)位置，纸条2到达(i2,j2)位置的最优值。则有， 其中 (i1,j1) (i2,j2) 1=i1, i2=M, 1=j1 , j2=N 时间复杂度O(N2M2),分析2,另一种思路：每个纸条都需要走M+N步才能达到目标。 因此，设F(k,i1,i2)表示两个纸条都走了K步，第1个纸条横坐标为i1,第2个纸条横坐标为i2的最优值。 则两个纸条的纵坐标分别为j1=K-i1, j

7、2=K-i2 ,状态转移方程如下： 其中 i1i2 1=i1, i2=M,1=k=N+M 时间复杂度O(N+M)*M2),免费馅饼,SERKOI最新推出了一种叫做“免费馅饼”的游戏。 游戏在一个舞台上进行。舞台的宽度为W格，天幕的高度为H格，游戏者占一格。开始时，游戏者站在舞台的正中央，手里拿着一个托盘。 游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或右移动一格或两格，也可以站在愿地不动。 馅饼有很多种，游戏者事先根据自己的口味，对各种馅饼依次打了分。同时在8-308电脑的遥控下，各种馅饼下落的速度也是不一样的，下落速度以格/秒为单位。当

8、馅饼在某一秒末恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼。 写一个程序，帮助我们的游戏者收集馅饼，使得收集的馅饼的分数之和最大。,输入数据： 第一行:宽度W（199奇数）和高度H（1 100整数） 接下来给出了一块馅饼信息。由4个正整数组成，分别表示了馅饼的 初始下落时刻、水平位置、下落速度、分值。 游戏开始时刻为0。从1开始自左向右依次对水平方向的每格编号。 输出数据： 收集到的馅饼最大分数之和。,由上图可知，尽管下落了4个馅饼，但只能接到3个： 第1时刻可以接到分值为5的馅饼 第2时刻可以接到分值为3的馅饼 第3时刻可以接到分值为4的馅饼 因此馅饼的总分值为5+3+4=12,分析

9、,由于馅饼下落的时间和速度都不同，人只能向左右移动，馅饼只能向下移动。人和馅饼都同时移动，思考起来比较复杂，因此我们需要转变思路：,算出每个时刻落到最底层的每个格子有多少分值的馅饼。 如果将馅饼当成参照物，则馅饼向下落，可以看成馅饼不动，人往上走去摘取馅饼，这样人每1时刻都可以走到上一行的5个格子，如右图：,动态规划,计算出每个格子每个时刻可能达到的馅饼分值，填入W*H的天幕表。 其中Ci,j表示天幕的第i行第j列的馅饼分值，即第i时刻，馅饼落到最底行的馅饼分值。 设F(i,j)表示人走到第i行j列所取得的馅饼最大分值和，则有， 0=i=T,1=j=W,决策数为5个 时间复杂度为O(5WT),

10、三角蛋糕,一块边长为n的正三角形的大蛋糕，一些被老鼠咬坏了，如下图黑色部分。 现想把该蛋糕切出一块最大的没被老鼠咬坏正三角形的蛋糕； 求切出的最大的三角形面积 n100。,向上的三角形，,设顶点坐标为(i,j)的三角形最大高度为F(i,j) 显然： F(i,j)=MINF(i-1,j-1),F(i-1,j+1) +1， 当Ci-1,j=-，表示这个三角形没被老鼠咬坏。,向下的三角形,设顶点坐标为(i,j)的三角形最大高度为G(i,j) 显然： G(i,j)=MING(i+1,j-1),G(i+1,j+1) +1， 当Ci+1,j=-，表示这个三角形没被老鼠咬坏。,分析,分别求F(i,j)和G(

11、i,j) 1=i=n,1=j=2n-1 因此，时间复杂度O(N2) 答案为高度的平方，证明如下： 假设最大高度为W 则三角形个数为+2W-1=W2,主程序,for i:=1 to n do倒三角情况 for j:=i to 2*n-i do if (ci,j=-)and(i mod 2=j mod 2) then如果该位置没被吃，而且必须是头朝下的三角 begin if ci-1,j- then fi,j:=1 else fi,j:=min(fi-1,j-1,fi-1,j+1)+1;是否可以从上面的位置转移过来堆成更大的三角形 if fi,jans then ans:=fi,j; end; 正三角情况