选拔赛-杀伤力

杀伤力

Time Limit : 3000/1000ms (Java/Other)   Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 46   Accepted Submission(s) : 13

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

有一个游戏,提供你两种资源MIN和GAS. 然后可以购买ZE,ST,SE三种设备武装你的军队.每单位ZE需要花费100 MIN ,但不需要GAS.每单位ST需要花费125 MIN和 50 GAS.每单位SE需要花费50 MIN和 100 GAS.

给定资源量和每种设备的杀伤值,求如何装备军队使得杀伤力最大  

Input

输入含多个测试用例，每行一个测试用例。每个测试用例有5个整数. M (0<=M<=50000),你拥有的MIN数量.G (0<=G<=50000), 你拥有的GAS数量. Z (0 <= Z<=1000), 每个ZE的杀伤值. S (0<= S<=1000), 每个ST的杀伤值. E

(0<=E<=1000) ,每个SE的杀伤值. 输入M = G =Z =S = E = 0表示结束,不应该处理.

Output

对每个测试用例,单独一行输出最大的杀伤力

Sample Input

500 400 10 20 15

0 0 0 0 0

Sample Output

95

Author

hnust_loser

思路：一开始用背包搞了许久未果，后来注意到数据较小，暴力过之，赛后与同学交流，发现确实有人背包过，自己还是弱爆了啊 。

#include<stdio.h>
int main()
{
    int m,g,z,s,e;
    int i,j,l1,l2;
    while(scanf("%d%d%d%d%d",&m,&g,&z,&s,&e)!=EOF)
    {
        if(m==0&&g==0&&z==0&&s==0&&e==0)
            break;        
        l1=m/100;
        l2=(m/125)<(g/50)?(m/125):(g/50);
        int max=0;
        for(i=0;i<=l1;i++)
        {
            for(j=0;j<=l2&&(j*125+i*100)<=m;j++)
            {
                int x1=(m-100*i-125*j)/50;
                int x2=(g-50*j)/100;
                int x3=x1<x2?x1:x2;
                if(i*z+j*s+x3*e>max)
                    max=i*z+j*s+x3*e;
            }
        }
        printf("%d\n",max);
    }
    return 0;
}