【poj 1925】Spiderman 题意＆题解＆代码（Ｃ＋＋）

题目链接：

http://poj.org/problem?id=1925

题意：

输入Ｋ组数据，每组数据输入ｎ个柱子的信息，每个柱子信息为ｘ坐标和高度ｈ，蜘蛛侠需要从第一的柱子通过不断荡蛛丝荡到最后一个柱子，荡的规则：
１．蜘蛛侠不会撞到柱子上，假如他在高度为ｈ的位置ｊ通过柱子ｉ前进，那么它会直接荡到同样高度为ｈ位置为ｘ[ｉ]＋ｘ[ｉ]－ｊ的位置上，不会受中间柱子的阻挡（ｘ[ｉ]表示柱子ｉ的ｘ坐标）
２．蜘蛛侠在荡蛛丝的过程中一旦能荡到位置ｘ，使得ｘ>=ｘ[ｎ]，则视为它荡到了最后一个柱子上（只适用于最后一个柱子）。
求最少的荡蛛丝的次数。

1 <= Ｔ <= 20，0 <= Xｉ, Yｉ <= 1000000，2 <= N <= 5000

题解：

注意它给出了初始的高度，每次荡完之后所处位置的高度与初始高度相同，因此高度仅仅用来判断能否荡蛛丝，对于状态转移并没有影响。

首先不考虑数据范围，我们很快可以想出一个Ｎ×Ｘ[ｎ]的做法，类似于01背包，dp[ｊ]表示到达位置ｊ时所荡的最少次数，转移方程和01背包也没太大区别

        for (int i=1;i<=x[n];i++)
        dp[i]=55555; 
        dp[0]=0;
        for (int i=2;i<=n;i++)
        for (int j=0;j<=x[i];j++)
        if (dp[j]!=55555&&pan(i,j))
        {
            int nex=min(x[i]+x[i]-j,x[n]);
            dp[nex]=min(dp[nex],dp[j]+1);
        }

然而这样的时间复杂度妥妥的超时，参考了一下题解，我们发现每个柱子所能更新的区间范围是一定的（因为蛛丝的长度要求），范围的大小len

            int len=pow(h[i],2)-pow(h[i]-h[1],2);
            len=sqrt(len);

从(　０　,　x[ｉ]－len　)这部分是根本不能通过柱子ｉ往前荡的，这部分没用的枚举浪费了很多时间复杂度，那么我们每次从（ｘ[ｉ]－ｌｅｎ）的位置开始枚举到ｘ[ｉ]即可，虽然感觉这样会有数据能够使它卡掉，因为按数学式子写时　len^2=(hi^2)-(hi-h0)^2，我们发现当hi和h0都最大且相近时，时间还是会超时，然而加了这优化后至少poj是能过的，醉了。

代码：

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<cmath>
using namespace std;
int T,n,x[5005],h[5005],dp[1000005];
bool pan(int i,int w)
{
    if (pow(h[i],2)>=pow(x[i]-w,2)+pow(h[i]-h[1],2)) return 1;
    return 0;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
        scanf("%d%d",&x[i],&h[i]);
        for (int i=1;i<=x[n];i++)
        dp[i]=55555; 
        dp[0]=0;
        for (int i=2;i<=n;i++)
        {
            int len=pow(h[i],2)-pow(h[i]-h[1],2);
            len=sqrt(len);
            for (int j=max(x[i]-len,0);j<=x[i];j++)
            if (dp[j]!=55555&&pan(i,j))
            {
                //这里之所以加pan(i,j)是因为担心精度处理出问题，去掉之后会ＷＡ
                int nex=min(x[i]+x[i]-j,x[n]);
                dp[nex]=min(dp[nex],dp[j]+1);   
            }
        }
                if (dp[x[n]]!=55555)
            printf("%d\n",dp[x[n]]);         
                else printf("-1\n");
    }
}