【题意】
给定n个塔的横坐标和高度,保证高度各不相同且横坐标递增,蜘蛛侠可以向一个塔射蛛丝然后荡到当前的相对位置,求最少要用多少次蛛丝
【输入】
多组数据,第一行一个t表示数据组数
每组数据第一行一个n
接下来n行为塔的横坐标和高度
【输出】
对于每组数据,输出一个数字表示最少要用多少次蛛丝
读英文题比较有难度,对于这道题来说,荡一次会到对于塔的轴对称位置,所以横坐标是不变的
所以dp,f[i]表示荡到横坐标为i所需蛛丝最小次数
program poj1925; var ans,n,i,j,k:longint; x,y:array [0..5001] of int64; f:array [0..1000001] of longint; function max (a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; function min (a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; begin read(k); while k>0 do begin dec(k); read(n); for i:=1 to n do read(x[i],y[i]); fillchar(f,sizeof(f),63); f[0]:=0; ans:=f[1000001]; for i:=1 to n-1 do for j:=1 to trunc(sqrt(y[i]*y[i]-(y[i]-y[1])*(y[i]-y[1]))) do if x[i]-j>=0 then if x[i]+j>=x[n] then ans:=min(ans,f[x[i]-j]+1) else f[x[i]+j]:=min(f[x[i]+j],f[x[i]-j]+1); for i:=1 to trunc(sqrt(y[n]*y[n]-(y[n]-y[1])*(y[n]-y[1]))) do ans:=min(ans,f[x[n]-i]+1); if ans=f[1000001] then writeln(-1) else writeln(ans); end; end.