首页 > 代码库 > ACdream1092

ACdream1092

2024-07-13 03:54:26   225人阅读

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

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

直接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 1010using 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[0]=m[0].x=m[0].y=m[0].t=0;    scanf("%d",&T);    while (T--)    {        ans=0;        scanf("%d%d",&n,&v);        for (int i=1; i<=n; i++)            scanf("%lf%lf%lf%lf",&m[i].x,&m[i].y,&m[i].t,&m[i].p),sum[i]=0;        sort(m+1,m+1+n,cmp);        for (int i=1; i<=n; i++)        {            for (int j=0; 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 0;}


联系
我们