poj 1925 spiderman

首先，这道题有两种做法。第一种是先枚举位置，再枚举楼进行dp。第二种是先枚举楼，再枚举位置。
然而蜘蛛侠的行进路线有对称性的。相当于将一号楼沿着某一座楼对称过来，就像镜子一样。根据对称性，蜘蛛侠在放出绳子时的高度永远是h[1]。

因此，第二种方法中枚举位置时，可以根据蜘蛛侠所在的高度和楼的高度两个条件，缩小第二层枚举的范围。因此，第二中方法更加优秀。

【代码】

[cpp] 
#include <iostream> 
#include <cstring> 
#include <string> 
#include <cstdio> 
#include <algorithm> 
using namespace std; 
 
const int N=5005,INF=N*2; 
 
int f[2000002],n; 
long long x[N],y[N]; 
 
int main() 
{ 
    int cc,i,j,ans; 
    long long d; 
 
    freopen("in","r",stdin); 
    scanf("%d",&cc); 
    while (cc--) 
    { 
        memset(f,20,sizeof(f)); 
        scanf("%d",&n); 
        for (i=1;i<=n;i++) 
            scanf("%lld%lld",&x[i],&y[i]); 
        f[x[1]]=0; 
        for (i=2;i<=n;i++) 
        { 
            for (j=x[i]-1;j>=x[1];j--) 
            { 
                d=(j-x[i])*(j-x[i])+(y[i]-y[1])*(y[i]-y[1]); 
                if (d>y[i]*y[i]) break; 
                f[2*x[i]-j]=min(f[2*x[i]-j],f[j]+1); 
            } 
        } 
        ans=INF; 
        for (i=x[n];i<=2*x[n];i++) 
            ans=min(ans,f[i]); 
        if (ans>=INF) ans=-1; 
        printf("%d\n",ans); 
    } 
} 

补充：软件开发 , C++ ,

上一个：池子法 邻接表建图
下一个：POJ 2057 The lost house