SSL_1637【苹果】

苹果

题目

农场的夏季是收获的好季节。在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)点，他最多能接到多少个苹果？

输入

第一行：两个整数，N(苹果个数，n<=5000)和S(速度)；第2…N+1行：每行三个整数Xi,Yi,Ti，表示每个苹果掉下的位置和落下的时间。

输出

仅一行，一个数，表示最多能接到几个苹果

Sample Input

5 3
0 0 1
0 3 2
-5 12 6
-1 0 3
-1 1 2

Sample Output

3

注：样例是（1，5，4）

---

解题思路

DP要划分阶段，这道题的阶段是时间，所以定义一个结构体node，并使用sort排序我才不会说我是懒得打冒泡排序时间，随后我们枚举每一个苹果，判断能不能接到，素质longlong

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
long long n,m,maxn,b[6001];
struct node
{
 long long x,y,z;
}a[6001];
bool cmp(node a,node b)
{
 return a.z<b.z;
}
double d(long long i,long long j)
{
 long long x=a[i].x-a[j].x,y=a[i].y-a[j].y;
 double z=sqrt(1.0*(x*x+y*y));
 return z;
}
int main()
{
 scanf("%lld%lld",&n,&m);
 for(long long i=1;i<=n;i++)
 {
  scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].z);
 }
 sort(a+1,a+n+1,cmp);
 for(long long i=1;i<=n;i++)
 {
  for(long long j=i-1;j>=0;j--)
  {
   if(j!=0&&b[j]==0)continue;
   if(d(i,j)<=(a[i].z-a[j].z)*1.0*m)b[i]=max(b[i],b[j]+1);//动态转移方程
  }
  maxn=max(maxn,b[i]);
 }
 printf("%lld",maxn);
 return 0;
}

本文地址：https://blog.csdn.net/zhanglili1597895/article/details/108173127