Dr.Octopus kidnapped Spiderman's girlfriend M.J.and kept her in the West Tower.Now the hero,Spiderman,has to reach the tower as soon as he can to rescue her,using his own weapon,the web.From Spiderman's apartment,where he starts ,to the tower there i
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/17 01:56:55
Dr.Octopus kidnapped Spiderman's girlfriend M.J.and kept her in the West Tower.Now the hero,Spiderman,has to reach the tower as soon as he can to rescue her,using his own weapon,the web.From Spiderman's apartment,where he starts ,to the tower there i
Dr.Octopus kidnapped Spiderman's girlfriend M.J.and kept her in the West Tower.Now the hero,Spiderman,has to reach the tower as soon as he can to rescue her,using his own weapon,the web.
From Spiderman's apartment,where he starts ,to the tower there is a straight road.Alongside of the road stand many tall buildings,which are definitely taller or equal to his apartment.Spiderman can shoot his web to the top of any building between the tower and himself(including the tower),and then swing to the other side of the building.At the moment he finishes the swing,he can shoot his web to another building and make another swing until he gets to the west tower.
上面的描述是一道ACM训练题的部分,如有哪位朋友见过此道题,能否解说下如何求解的,还有这道题能不能用动态规划的算法来求解?能用或不能用都请说明详细理由!如果说的好,
Dr.Octopus kidnapped Spiderman's girlfriend M.J.and kept her in the West Tower.Now the hero,Spiderman,has to reach the tower as soon as he can to rescue her,using his own weapon,the web.From Spiderman's apartment,where he starts ,to the tower there i
先鄙视一下楼上的SB,接下来再回答楼主的问题.
这道题貌似是2004北京预选赛的题目.
就把我的大概做法说一下,希望对你有用.
这道题目的动规其实也不是很难想,因为每次shoot web的时候,spiderman总是在一次swing的终点,而这个终点的y坐标肯定是他的起始点的y坐标,每次swing的终点的y坐标都是一样.所以当我们选定一座building的时候,要求他怎么到达这座building,先求他最远能从离这个building多远的地方发射web.自然,这个距离就是distance=x[i]-(int)(sqrt((double)y[i]*y[i]-(double)(y[i]-y[0])*(y[i]-y[0]))+1e-12),所以在这一段distance之间所有的swing终点都能够shoot web到buildings[i].所以状态转移方程是这样：
solve[i]=min{solve[j]+1}(y[i]-distance