首页 > 代码库 > HDU 4563 御剑术I（背包）

HDU 4563 御剑术I（背包）

2024-07-09 00:17:31   220人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4563
题意：一个点开始在原点。有n个命令。第i个命令施加到这个点时，这个点的速度为(Vxi,Vyi)，即在x方向的速度为Vxi，在y方向的速度为Vyi。并且这个命令施加到点时之前的速度全部消失。每种命令最多使用一次。问在x方向走长度为m时在y方向的最大高度是多少？每种命令只能在整数时刻施加。
思路：首先，每种命令使用的先后顺序显然是没有关系的。除了最后一个施加的命令，之前的命令必然都是使用了整数秒。那么我们枚举每个命令作为最后一个命令，剩下的n-1个命令进行背包DP，f[i][j]表示前i个命令走长度为j的最大高度。最后枚举最后一个命令使用的时间即可。

 

double f[N][N];int a[N],b[N],n,m;double up(double &x,double y){    if(x<y) x=y;}void DP(){    int i,j,k;    FOR1(i,n) FOR0(j,m+1) f[i][j]=-inf;    double temp;    for(i=0;i*a[1]<=m;i++) f[1][i*a[1]]=b[1]*i-4.9*i*i;    for(i=2;i<n;i++) for(j=0;j<=m;j++) for(k=0;k*a[i]+j<=m;k++)    {        temp=f[i-1][j]+b[i]*k-4.9*k*k;        up(f[i][k*a[i]+j],temp);    }}double cal(){    if(n==1) return b[1]*(1.0*m/a[1])-4.9*sqr(1.0*m/a[1]);    int i,j,k;    double ans=-inf,temp,t;    FOR1(i,n)    {        swap(a[i],a[n]); swap(b[i],b[n]);        DP();        for(j=0;j<=m;j++)        {            t=1.0*j/a[n];            temp=f[n-1][m-j]+b[n]*t-4.9*t*t;            up(ans,temp);        }        swap(a[i],a[n]); swap(b[i],b[n]);    }    return ans;}int main(){    int num=0;    rush()    {        RD(n,m);        int i;        FOR1(i,n) RD(a[i],b[i]);        printf("Case %d: ",++num);        PR(cal());    }}

 

 

 


联系
我们