资源描述：
《dp-坐标规则型动态规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、坐标规则型动态规划长沙市雅礼中学朱全民Robots在一个n*m的棋盘内，一些格子里有垃圾要拾捡。现在有一个能捡垃圾的机器人从左上格子里出发，每次只能向右或者向下走。每次他到达一个点，就会自动把这个点内的垃圾拾掉。问：最多能拾多少垃圾。在最多的情况下，有多少种拾垃圾方案？数据范围:n<=100,m<=100样例分析最多能拾5块。有4种方法。分析(1)因为机器人只能向右或者向下走。符合无后效性原则。于是考虑动态规划。设F(i,j)表示从(1,1)点开始走到(i,j)的时候，最多捡了多少垃圾。F(i,j)=
2、Max{f(i-1,j),f(i,j-1)}+c[i,j]其中C[i,j]=1表示(i,j)点有垃圾。C[i,j]=0表示没有1<=i<=n,1<=j<=m，决策2种时间复杂度为O(n*m)分析(2)设G[i,j]表示在f[i,j]最大的时候，有多少种方案。捡到f(i,j)的垃圾只能从两个方向来走，方案数累加即可。因此，g(i,j)=g[i-1,j]*k+g[i,j-1]*L如果f[i-1,j]+c[i,j]=f[i,j]，则K=1否则K=0。如果f[i,j-1]+c[i,j]=f[i,j]，则L=1
3、否则L=0时间复杂度O(n*m)矩阵取数游戏（NOIP2007）对于一个给定的n*m的矩阵，矩阵中的每个元素aij为非负整数。游戏规则如下：1.每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有的元素；2.每次取走的各个元素只能是该元素所在行的行首或行尾；3.每次取数都有一个得分值，为每行取数的得分之和；每行取数的得分=被取走的元素值*2i，其中i表示第i次取数（从1开始编号）；4.游戏结束总得分为m次取数得分之和。求出取数后的最大得分。样例输入23 123 342输出82第1次：第一行取行
4、首元素，第二行取行尾元素，本次的氛围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行求值可以独立考虑！设f[i,j]表示区间i-j
5、的最优值f[i,j]=max{f[i+1,j]+w*a[i] , f[i,j-1]+w*a[j]}其中w=w+w,即w*2需要做若干次高精度加法和乘法。直到求出，max{f[i,i]+w*a[i]，i=1..m}为止。传纸条(NOIP2008)小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。班里每个同学都可以帮他们传递，但只会帮他们一次。每个同学愿意帮忙的好感度有高有低，可以用一个0-1
6、00的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度只和最大。现在，请你帮助小渊和小轩找到这样的两条路径。1<=m,n<=50贪心很容易想到一个算法：求出1个纸条从（1，1）到（M,N）的路线最大值.删除路径上的点值再求出1个纸条从（M,N）到（1，1）的路线最大值.统计两次和上述算法很容易找出反例，如下图。第1次找最优值传递后，导致第2次无法传递。分析贪心算法错误，因此我们需要同时考虑两个纸条的传递。由于小渊
7、和小轩的路径可逆，因此，尽管出发点不同，但都可以看成同时从(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
8、,j2=K-i2,状态转移方程如下：其中i1<>i21<=i1,i2<=M,1<=k<=N+M时间复杂度O((N+M)*M2)免费馅饼SERKOI最新推出了一种叫做“免费馅饼”的游戏。游戏在一个舞台上进行。舞台的宽度为W格，天幕的高度为H格，游戏者占一格。开始时，游戏者站在舞台的正中央，手里拿着一个托盘。游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或右移动一格或两格，也可以站在愿地不动。馅饼有很多种
