首页 > 代码库 > POJ1054 The Troublesome Frog [dp]
POJ1054 The Troublesome Frog [dp]
艰难的写上一篇,小学期太累了,,,很难坚持刷
#include <iostream> #include <cmath> #include <cstring> #include <cstdio> #include <cstdlib> #include <algorithm> using namespace std; int m,n; int num; struct Grid { int x,y; }grid[5555]; int cmp(const void* a,const void* b) { Grid* one; Grid* two; one=(Grid* ) a; two=(Grid* ) b; return ((one->x)==(two->x))?(one->y)-(two->y):(one->x)-(two->x); } int getstep(Grid grs,int dx,int dy) { int step=0; while(grs.x<=n&&grs.x>=1 &&grs.y>=1&&grs.y<=m) { if(!bsearch(&grs,grid,num,sizeof(Grid),cmp)) { step=0; break; } else { grs.x+=dx,grs.y+=dy; step++; } } return step; } int main() { //ios::sync_with_stdio(false); //freopen("/home/rainto96/in.txt","r",stdin); while(scanf("%d%d",&m,&n)!=EOF) { scanf("%d",&num); for(int i=0;i<=num;i++) { int xx,yy; scanf("%d%d",&xx,&yy); grid[i].x=yy,grid[i].y=xx; } qsort(grid,num,sizeof(Grid),cmp); int maxn=2; for(int i=0;i<num-1;i++) { for(int j=i+1;j<num;j++) { int dx,dy,px,py; dx=grid[j].x-grid[i].x; dy=grid[j].y-grid[i].y; px=grid[i].x-dx; py=grid[i].y-dy; if(py>=1&&py<=m&&px>=1&&px<=n) continue; if(grid[i].x+maxn*dx>n) break; py = grid[i].y + maxn * dy; if ( py > m || py < 1) continue; int step=getstep(grid[i],dx,dy); maxn=max(maxn,step); } } maxn=(maxn==2?0:maxn); printf("%d\n",maxn); } return 0; }
学会了二维的二分,其实就一句话
用 法: void *bsearch(const void *key, const void *base, size_t nelem, size_t width, int(*fcmp)(const void *, const *));
语法:
#include <stdlib.h> void *bsearch( const void *key, const void *buf, size_t num, size_t size, int (*compare)(const void *, const void *) );
参数:第一个:要查找的关键字。第二个:要查找的数组。第三个:指定数组中元素的数目。第四个:每个元素的长度(以字符为单位)。第五个:指向比较函数的指针。
功能: 函数用折半查找法在从数组元素buf[0]到buf[num-1] 匹配参数key。如果函数compare 的第一个参数小于第二个参数,返回负值;如果等于返回零值;如果大于返回正值。数组buf 中的元素应以升序排列。函数bsearch()的返回值是指向匹配项,如果没有发现匹配项,返回NULL
这个问题看起来很复杂,其实目的很简单:帮助农民找到为害最大的青蛙。也就是要找到
一条穿越稻田的青蛙路径,这个路径上被踩踏的水稻不少于其他任何青蛙路径上被踩踏的水稻数。当然,整个稻田中也可能根本就不存在青蛙路径。问题的关键是:找到穿越稻田的全
部青蛙路径。任何一条穿越稻田的青蛙路径L,至少包括3 棵被踩踏的水稻。假设其中前两
棵被踩踏的水稻分别是(X1,Y1)、(X2,Y2),那么:
令dx=X2-X1、dy=Y2-Y1;X0=X1-dx、Y0=Y1- dy;X3=X2 + dx、Y3=Y2 + dy
(X0,Y0)位于稻田之外,青蛙从该位置经一跳后进入稻田、踩踏位置(X1,Y1)上的水稻
(X3,Y3)位于稻田之内,该位置是L 上第3 棵被青蛙踩踏的水稻
Xi=X0 + idx、Yi=Y1 + idy(i3),如果(Xi,Yi)位于稻田之内,则(Xi,Yi)上的水稻必被
青蛙踩踏
根据上述规则,只要知道一条青蛙路径上的前两棵被踩踏的水稻,就可以找到该路径上其
他的水稻。为了找到全部的青蛙路径,只要从被踩踏的水稻中,任取两棵水稻(X1,Y1)、(X2,
Y2),判断(X1,Y1)、(X2,Y2)是否能够作为一条青蛙路径上最先被踩踏的两颗水稻。
解决方案
这个问题的描述中,最基本的元素是被踩踏的水稻。在程序中要选择一个合适的数据结构,
来表达这个基本元素。这个数据结构是否合适的标准是:在程序中要表达这个元素时,能否
用一个单词或者短语,即用一个变量来表示。
struct PLANT {//描述一棵被踩踏的水稻
int x; //水稻的行号
int y; //水稻的列号
}
这个问题的主要计算是:从被踩踏的水稻中选择两棵(X1,Y1)、(X2,Y2)。判断它们是否
能够作为一条青蛙路径上最先被踩踏的两颗水稻。(X1,Y1)、(X2,Y2)唯一确定了蛙跳的方
向和步长,从(X2,Y2)开始,沿着这个方向和步长在稻田内走。每走一步,判断所到达位置
上(X,Y)的水稻是否被踩踏,直到走出稻田为止。如果在某一步上,(X,Y)没有被踩踏,
则表明(X1,Y1)、(X2,Y2)是一条青蛙路径上最先被踩踏的两颗水稻的假设不成立。这个判
断的算法在问题求解过程中要反复使用,它的效率成为决定整个计算效率的关键。
用一个PLANT 型的数组plants[5001]表示全部被踩踏的水稻
将plants 中的元素按照行/列序号的升序(或者降序)排列
采用二分法查找plants 中是否有值为(X,Y)的元素:将(X,Y)与plants 中间的元素比较,
(1)相等,表明找到了元素;(2)比plants 中间元素的小,继续在plants 的前半部寻找;(3)
比plants 中间元素的大,继续在plants 的后半部寻找。
采用上述方法判断每走一步所到达位置上(X,Y)的水稻是否被踩踏,最多只要比较Log2N,
其中N 是稻田中被踩踏水稻的总量。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。