poj1925(dp)

链接：点击打开链接

题意：给出在x轴上的n座塔的坐标和高度，现要从第一座塔通过中间的塔发射绳索荡到最后一座塔，问最少发射几次绳索，具体看图

代码：

#include <queue>
#include <math.h>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int siz=1000005;
const int INF=0x3f3f3f3f;
int dp[siz];
long long x[siz],y[siz];
int main(){
    int t,n,i,j,st,en,tmp;
    scanf("%d",&t);
    while(t--){                                 //用坐标进行dp，主要要
        scanf("%d",&n);                         //想到能量守恒，每次高度不变...
        for(i=1;i<=n;i++)
        scanf("%lld%lld",&x[i],&y[i]);
        memset(dp,INF,sizeof(dp));
        dp[x[1]]=0;
        for(i=2;i<=n;i++){
            tmp=(int)sqrt(y[i]*y[i]*1.0-(y[i]-y[1])*(y[i]-y[1])*1.0);
            for(j=1;j<=tmp;j++){
                if(x[i]-j<x[1])                 //不能超过起点
                break;
                st=x[i]-j;
                en=min(x[n],x[i]+j);
                if(i==2)
                if(dp[st]==INF)
                continue;                       //相当于由对称位置转移过来
                dp[en]=min(dp[en],dp[st]+1);
            }
        }
        if(dp[x[n]]==INF)
        puts("-1");
        else
        printf("%d\n",dp[x[n]]);
    }
    return 0;
}