ACdream1092

时间:2023-03-10 05:37:44
ACdream1092

题意是给出某个地鼠的出现位置以及出现时间,人有一个移动速度,求此人最多可以打多少个地鼠?

我们根据时间把所有的地鼠排序,如果两个地鼠之间的距离不超过时间只差与速度的乘积,那说明打完上一只地鼠还可以打到这一只地鼠。

直接f[i]表示打完第i只地鼠且此时在i地鼠位置的期望,DP即可。

召唤代码君:

/*
* this code is made by 092000
* Problem: 1092
* Verdict: Accepted
* Submission Date: 2014-07-19 23:27:11
* Time: 276MS
* Memory: 1732KB
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define maxn 1010
using namespace std; struct mouse{
double x,y,t,p;
}m[maxn]; bool cmp(mouse m1,mouse m2)
{
return m1.t<m2.t;
} int T,n,v;
double ans,sum[maxn]; double dis(int i,int j)
{
return sqrt((m[i].x-m[j].x)*(m[i].x-m[j].x)+(m[i].y-m[j].y)*(m[i].y-m[j].y));
} int main()
{
sum[]=m[].x=m[].y=m[].t=;
scanf("%d",&T);
while (T--)
{
ans=;
scanf("%d%d",&n,&v);
for (int i=; i<=n; i++)
scanf("%lf%lf%lf%lf",&m[i].x,&m[i].y,&m[i].t,&m[i].p),sum[i]=;
sort(m+,m++n,cmp);
for (int i=; i<=n; i++)
{
for (int j=; j<i; j++)
if (dis(i,j)<=(m[i].t-m[j].t)*v) sum[i]=max(sum[i],sum[j]);
ans=max(ans,sum[i]=sum[i]+m[i].p);
}
printf("%.6f\n",ans);
}
return ;
}