DP-坐标规则型动态规划

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,坐标规则型动态规划,长沙市雅礼中学 朱全民,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,的矩阵，矩阵中的每个元素,a,ij,为非负整数。游戏规则如下：,1.,每次取数时须从每行各取走一个元素，共,n,个。,m,次后取完矩阵所有的元素；,2.,每次取走的各个元素只能是该元素所在行的行首或行尾；,3.,每次取数都有一个得分值，为每行取数的得分之和；每行取数的得分,=,被取走的元素值*,2,i,，其中,i,表示第,i,次取数（从,1,开始编号）；,4.,游戏结束总得分为,m,次取数得分之和。,求出取数后的最大得分。,样例,输入,2 31 2 33 4 2,输出,82,第,1,次：第一行取行首元素，第二行取行尾元素，本次的氛围,1*2,1,+2*2,1,=6,第,2,次：两行均取行首元素，本次得分为,2*2,2,+3*2,2,=20,第,3,次：得分为,3*2,3,+4*2,3,=56,。总得分为,6+20+56=82,数据范围,60%,的数据满足：,1=,n,m,=30,，答案不超过,10,16,100%,的数据满足：,1=,n,m,=80,，,0=,a,ij,=1000,1*2,1,+2*2,1,=6,2*2,2,+3*2,2,=20,3*2,3,+4*2,3,=56,1*2,1,+2*2,2+,3*2,3=,2*2,1+,3*2,2+,4*2,3,分析,首先，,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(i,1,j,1,i,2,j,2,),表示纸条,1,到达,(i,1,j,1,),位置，纸条,2,到达,(i,2,j,2,),位置的最优值。则有，,其中,(i,1,j,1,)(i,2,j,2,),1=i,1,i,2,=M,1=j,1,j,2,=N,时间复杂度,O(N,2,M,2,),分析,2,另一种思路：每个纸条都需要走,M+N,步才能达到目标。,因此，设,F(k,i,1,i,2,),表示两个纸条都走了,K,步，第,1,个纸条横坐标为,i,1,第,2,个纸条横坐标为,i,2,的最优值。,则两个纸条的纵坐标分别为,j,1,=K-i,1,j,2,=K-i,2,状态转移方程如下：,其中,i,1,i,2,1=i,1,i,2,=M,1=k=N+M,时间复杂度,O(N+M)*M,2,),免费馅饼,SERKOI,最新推出了一种叫做,“,免费馅饼,”,的游戏。,游戏在一个舞台上进行。舞台的宽度为,W,格，天幕的高度为,H,格，游戏者占一格。开始时，游戏者站在舞台的正中央，手里拿着一个托盘。,游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或右移动一格或两格，也可以站在愿地不动。,馅饼有很多种，游戏者事先根据自己的口味，对各种馅饼依次打了分。同时在,8-308,电脑的遥控下，各种馅饼下落的速度也是不一样的，下落速度以格,/,秒为单位。当馅饼在某一秒末恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼。,写一个程序，帮助我们的游戏者收集馅饼，使得收集的馅饼的分数之和最大。,输入数据：,第一行,:,宽度,W,（,199,奇数）和高度,H,（,1 100,整数）,接下来给出了一块馅饼信息。由,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,的正三角形的大蛋糕，一些被老鼠咬坏了，如下图黑色部分。,现想把该蛋糕切出一块最大的没被老鼠咬坏正三角形的蛋糕；,求切出的最大的三角形面积,n,100,。,向上的三角形，,设顶点坐标为,(,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=j,ans,then,ans,:=,fi,j,;,end;,正三角情况程序与上类似,总结,规则类动态规划有一个共性，那就是在一个矩阵中（一般是二维矩阵，当然可能有更加复杂的图形）给出一些规则，然后按规则去做某些决策，我们思考这类问题的基本方法是：以坐标为状态，坐标之间的转换关系，一般利用问题给出的规则进行决策转移。如下图。,状态转移方程一般可描述如下：,F(i,j,)=Maxf(i-1,k)+,决策；这里,k,为规则数,