DP-坐标规则型动态规划.ppt

坐标规则型动态规划,长沙市雅礼中学朱全民,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表示(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次后取完矩阵所有的元素；2.每次取走的各个元素只能是该元素所在行的行首或行尾；3.每次取数都有一个得分值，为每行取数的得分之和；每行取数的得分=被取走的元素值*2i，其中i表示第i次取数（从1开始编号）；4.游戏结束总得分为m次取数得分之和。求出取数后的最大得分。,样例,输入23123342输出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，答案不超过1016100%的数据满足：1=n,m=80，0=aij=10001*21+2*21=62*22+3*22=203*23+4*23=561*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)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。班里每个同学都可以帮他们传递，但只会帮他们一次。每个同学愿意帮忙的好感度有高有低，可以用一个0-100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度只和最大。现在，请你帮助小渊和小轩找到这样的两条路径。1=m,n=50,贪心,很容易想到一个算法：求出1个纸条从（1，1）到（M,N）的路线最大值.删除路径上的点值再求出1个纸条从（M,N）到（1，1）的路线最大值.统计两次和上述算法很容易找出反例，如下图。第1次找最优值传递后，导致第2次无法传递。,分析,贪心算法错误，因此我们需要同时考虑两个纸条的传递。由于小渊和小轩的路径可逆，因此，尽管出发点不同，但都可以看成同时从(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,j2=K-i2,状态转移方程如下：其中i1i21=i1,i2=M,1=k=N+M时间复杂度O(N+M)*M2),免费馅饼,SERKOI最新推出了一种叫做“免费馅饼”的游戏。游戏在一个舞台上进行。舞台的宽度为W格，天幕的高度为H格，游戏者占一格。开始时，游戏者站在舞台的正中央，手里拿着一个托盘。游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或右移动一格或两格，也可以站在愿地不动。馅饼有很多种，游戏者事先根据自己的口味，对各种馅饼依次打了分。同时在8-308电脑的遥控下，各种馅饼下落的速度也是不一样的，下落速度以格/秒为单位。当馅饼在某一秒末恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼。写一个程序，帮助我们的游戏者收集馅饼，使得收集的馅饼的分数之和最大。,输入数据：第一行:宽度W（199奇数）和高度H（1100整数）接下来给出了一块馅饼信息。由4个正整数组成，分别表示了馅饼的初始下落时刻、水平位置、下落速度、分值。游戏开始时刻为0。从1开始自左向右依次对水平方向的每格编号。输出数据：收集到的馅饼最大分数之和。,由上图可知，尽管下落了4个馅饼，但只能接到3个：第1时刻可以接到分值为5的馅饼第2时刻可以接到分值为3的馅饼第3时刻可以接到分值为4的馅饼因此馅饼的总分值为5+3+4=12,分析,由于馅饼下落的时间和速度都不同，人只能向左右移动，馅饼只能向下移动。人和馅饼都同时移动，思考起来比较复杂，因此我们需要转变思路：,算出每个时刻落到最底层的每个格子有多少分值的馅饼。如果将馅饼当成参照物，则馅饼向下落，可以看成馅饼不动，人往上走去摘取馅饼，这样人每1时刻都可以走到上一行的5个格子，如右图：,动态规划,计算出每个格子每个时刻可能达到的馅饼分值，填入W*H的天幕表。其中Ci,j表示天幕的第i行第j列的馅饼分值，即第i时刻，馅饼落到最底行的馅饼分值。设F(i,j)表示人走到第i行j列所取得的馅饼最大分值和，则有，0=i=T,1=j=W,决策数为5个时间复杂度为O(5WT),三角蛋糕,一块边长为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(i,j)1=i=n,1=jansthenans:=fi,j;end;正三角情况程序与上类似,总结,规则类动态规划有一个共性，那就是在一个矩阵中（一般是二维矩阵，当然可能有更加复杂的图形）给出一些规则，然后按规则去做某些决策，我们思考这类问题的基本方法是：以坐标为状态，坐标之间的转换关系，一般利用问题给出的规则进行决策转移。如下图。状态转移方程一般可描述如下：F(i,j)=Maxf(i-1,k)+决策；这里k为规则数,