本文主要是介绍SSL 1637——苹果，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
农场的夏季是收获的好季节。在Farmer John的农场，他们用一种特别的方式来收苹果：Bessie摇苹果树，苹果落下，然后Farmer John尽力接到尽可能多的苹果。
作为一个有经验的农夫， Farmer John将这个过程坐标化。他清楚地知道什么时候(1<=t<=1,000,000)什么位置(用二维坐标表示，-1000<=x,y<=1000)会有苹果落下。他只有提前到达那个位置，才能接到那个位置掉下的苹果。
一个单位时间，Farmer John能走s(1<=s<=1000)个单位。假设他开始时(t=0)站在(0,0)点，他最多能接到多少个苹果？
Input
第一行：两个整数，N(苹果个数，n<=5000)和S(速度)；
第2..N+1行：每行三个整数Xi,Yi,Ti，表示每个苹果掉下的位置和落下的时间。
Output
仅一行，一个数，表示最多能接到几个苹果
Sample Input
5 3
0 0 1
0 3 2
-5 12 6
-1 0 3
-1 1 2
Sample Output
3 (Farmer John可以接到第1,5,4个苹果)
思路
先将苹果下落的时间从小到大排序
然后用dis(i,j)表示两点之间的距离为sqrt(sqr(x1-x2)+sqr(y1-y2))
如果从第i个苹果到第j个苹果所用的时间小于他的速度*（第i个苹果下落的时间-第j个苹果下落的时间），就f[i]:=max(f[i],f[j]+1)
代码如下：
const maxapp=5000;
type as=recordx,y,time:longint;
end;var f:array [0..maxapp] of longint;app:array[0..maxapp] of as;n,s:longint;i,j,ans:longint;m:real;procedure init;
var i,j,k:longint;
beginreadln(n,s);for i:=1 to n doreadln(app[i].x,app[i].y,app[i].time);app[0].x:=0; app[0].y:=0; app[0].time:=0;
end;procedure qsort(l,r: longint);
var i,j,x: longint;tmp:as;
begini:=l;j:=r;x:=app[(l+r) div 2].time;repeatwhile app[i].time<x do inc(i);while x<app[j].time do dec(j);if not(i>j) thenbegintmp:=app[i];app[i]:=app[j];app[j]:=tmp;inc(i);j:=j-1;end;until i>j;if l<j then qsort(l,j);if i<r then qsort(i,r);
end;function dis(i,j:longint):real;
begindis:=sqrt(sqr(app[i].x-app[j].x)+sqr(app[i].y-app[j].y));
end;begininit;qsort(1,n);f[0]:=0;ans:=0;for i:=1 to n dobeginf[i]:=0;for j:=0 to i-1 doif (j=0)or((j<>0)and(f[j]<>0)) thenbeginm:=dis(i,j);if ( m<=s*(app[i].time-app[j].time) )and( f[j]+1>f[i] )then f[i]:=f[j]+1;end;if f[i]>ans then ans:=f[i];end;write(ans);
end.这篇关于SSL 1637——苹果的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
