dp-坐标规则型动态规划

dp-坐标规则型动态规划

ID:39963762

大小:221.00 KB

页数:24页

时间:2019-07-16

dp-坐标规则型动态规划_第1页
dp-坐标规则型动态规划_第2页
dp-坐标规则型动态规划_第3页
dp-坐标规则型动态规划_第4页
dp-坐标规则型动态规划_第5页
资源描述:

《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格,游戏者占一格。开始时,游戏者站在舞台的正中央,手里拿着一个托盘。游戏开始后,从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或右移动一格或两格,也可以站在愿地不动。馅饼有很多种

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。