UC知道Spiderman
来源：百度知道 编辑：UC知道 时间：2024/05/24 09:44:41
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训练题的部分,如有哪位朋友见过此道题,能否解说下如何求解的,还有这道题能不能用动态规划的算法来求解?能用或不能用都请说明详细理由!谢谢!如果说的好,另再加分!!
先鄙视一下楼上的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<ends[j]<y[i])，ends数组是用来存每一次swing终点的x坐标的。希望上面说的能给楼主一些帮助，剩下的程序就由楼主自己完成吧，Good luck！
我做了，你看看吧！但是不知道能不能运行
import java.awt.*;
import java.awt.event.*;
import java.lang.*;
import javax.swing.*;
public class Counter extends Frame
{
//声明三个面板的布局
GridLayout gl1,gl2,gl3;
Panel p0,p1,p2,p3;
JTextField tf1;
TextField tf2;
Button b0,b1,b2,b3,b4,b5,b6,b7,b8,b9,b10,b11,b12,b13,b14,b15,b16,b17,b18,b19,b20,b21,b22,b23,b24,b25,b26;
StringBuffer str;//显示屏所显示的字符串
double x,y