首页 > ACM题库 > HDU-杭电 > HDU 4563-御剑术I-背包问题-[解题报告]HOJ
2015
07-25

HDU 4563-御剑术I-背包问题-[解题报告]HOJ

御剑术I

问题描述 :

在众多武侠类游戏中,都可以看到主角衣袂飘飘地在一旁通过“气”操控剑在空中飞行来杀伤敌人的帅气场景。

“十年磨一剑,霜刃未曾试”,在刻苦练习了不知道多少个日夜之后,今天你也掌握了这一项高超的武艺。虽然你可以并行地控制多柄剑同时飞行,但为了照顾普通群众的理解需求,暂时只考虑一把剑的情形。

所谓御剑术,实质上就是通过“气”来传递信息给已经通灵的剑,在这里,我们定义为瞬间给予剑一个设定好的速度。为了简化问题,将剑看作一个大小可以忽略的点,飞行在一个“二次元”――二维世界里,假设起点为原点(0,0)。需要注意的是,在这个世界中,剑依然会受到竖直向下的大小为g=9.8的重力加速度的影响。

现在由你来控制这个点,哦不,是剑,你已经掌握了N个命令,每个命令会瞬间清除剑的所有速度,然后给它一个固定的向量速度(V_xi, V_yi),分别表示水平速度与竖直速度,每个命令最多可发出一次。你的任务是,控制剑完成水平方向上长度为L的飞行,并使其完成飞行时的高度尽可能高,也就是,Y坐标值尽可能大。

由于你对“气”掌握的并不够熟练,所以只能在整数时刻时发出命令,可以认为这里的所有速度与加速度都转化为标准值(比如,米和秒),你只能在T=0,1,… 这种时刻下达指令。你希望知道横向飞行距离固定时最高的飞行高度。

输入:

输入第一行为T,表示有T组测试数据。
每组数据以两个整数N,L开始,含义与描述对应。接下来的N行中,每行有两个整数,V_xi与V_yi。

[Technical Specification]

1. 1 <= T <= 77
2. 1 <= N <= 100
3. 1 <= L <= 100
4. 1 <= V_xi <=100
5. -100 <= V_yi <= 100

输出:

输入第一行为T,表示有T组测试数据。
每组数据以两个整数N,L开始,含义与描述对应。接下来的N行中,每行有两个整数,V_xi与V_yi。

[Technical Specification]

1. 1 <= T <= 77
2. 1 <= N <= 100
3. 1 <= L <= 100
4. 1 <= V_xi <=100
5. -100 <= V_yi <= 100

样例输入:

3
1 1
10 10
2 10
10 10
10 20
3 30
10 10
10 15
10 20

样例输出:

Case 1: 0.951
Case 2: 15.100
Case 3: 30.500

Hint
如果御剑熟练一些,不需要在整数点发出命令,样例2的结果可以更大。但是这里,只能选择在T=0时发出命令(10,20),然后等待飞行完成。 注意,测试数据大部分都是纯随机生成的。

题目链接: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());
    }
}

 

 

 

参考:http://www.cnblogs.com/jianglangcaijin/p/3799549.html