Hdu6082度度熊与邪恶大魔王

阅读全文大概需要 4分钟
本文总阅读量
Posted by yjjr's blog on February 6, 2018

HDU6082度度熊与邪恶大魔王

标签:DP,背包问题

http://www.sakurasake.icoc.me/nd.jsp?id=10

Time Limit: 2000/1000 MS(Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Problem Description

度度熊为了拯救可爱的公主,于是与邪恶大魔王战斗起来。

邪恶大魔王的麾下有n个怪兽,每个怪兽有a[i]的生命值,以及b[i]的防御力。

度度熊一共拥有m种攻击方式,第i种攻击方式,需要消耗k[i]的晶石,造成p[i]点伤害。

当然,如果度度熊使用第i个技能打在第j个怪兽上面的话,会使得第j个怪兽的生命值减少p[i]-b[j],当然如果伤害小于防御,那么攻击就不会奏效。

如果怪兽的生命值降为0或以下,那么怪兽就会被消灭。

当然每个技能都可以使用无限次。

请问度度熊最少携带多少晶石,就可以消灭所有的怪兽。

 

Input

本题包含若干组测试数据。

第一行两个整数n,m,表示有n个怪兽,m种技能。

接下来n行,每行两个整数,a[i],b[i],分别表示怪兽的生命值和防御力。

再接下来m行,每行两个整数k[i]和p[i],分别表示技能的消耗晶石数目和技能的伤害值。

数据范围:

1<=n<=100000

1<=m<=1000

1<=a[i]<=1000

0<=b[i]<=10

0<=k[i]<=100000

0<=p[i]<=1000

 

 

Output

对于每组测试数据,输出最小的晶石消耗数量,如果不能击败所有的怪兽,输出-1

 

 

Sample Input

1 2

3 5

7 10

6 8

1 2

3 5

10 7

8 6

 

 

Sample Output

6

18

 

 

Source

2017"百度之星"程序设计大赛 - 资格赛

 

分析:

这题明显是个背包问题,但是仔细观察,发现用完全背包最正常的写法时间复杂度为O(n*m),肯定TLE,所以优化。看题目给出的数据大小,可以在计算时计算生命值从1-1000,防御值0-10的所有情况,然后将所有符合对应的情况的怪兽加起来,计算出消耗最小的晶石数量

具体一点说:把怪兽的生命值当成背包的体积,每个技能的伤害值当成每个物品的大小,每个技能的晶石数当成这个物品的花费,目的是把每个背包填满或更多,求每个背包的最小花费就可以了

对于第u个技能来说,如果p[u]<=j,说明根本打不出伤害,不用管。
反之,伤害则temp=p[u]-j这时候 又有两种情况:
如果temp>=j,说明靠这一个技能就够打出足够伤害了,那么肯定是用消耗晶石最少的那个技能

F[i][j]表示消灭生命力为i,防御值为j的怪物需要最小的晶石数

状态转移方程为:F[i][j]=min(f[i-(p[num]-j)][j]+k[num];

参考代码如下:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=100005;
const int maxm=1005;

LL a[maxn],b[maxn],k[maxm],p[maxm];
LL f[maxm][15];
inline LL max(LL a,LL b)
{
	return a>b?a:b;
}
inline LL min(LL a,LL b)
{
	return a<b?a:b;
}
int main()
{
	LL n,m;
	while(scanf("%lld%lld",&n,&m)!=EOF)
	{
		LL up1=0,up2=0,hp=0;
		for(int i=1;i<=n;i++)
		{
			a[i]=read(),b[i]=read();
			up1=max(up1,b[i]);
			hp=max(hp,a[i]);
		}
		for(int i=1;i<=m;i++)
		{
			k[i]=read(),p[i]=read();
			up2=max(up2,p[i]);
		}
		if(up1>=up2)
		{
			cout<<"-1\n";
			continue;
		}
		memset(f,0,sizeof(f));
        for(int i=1;i<=hp;i++)//穷举每个幽灵生命值--相当于背包中的总重量
            for(int j=0;j<=10;j++)//穷举每个幽灵防御值
            {
                f[i][j]=1e18;
                for(int num=1;num<=m;num++)//num魔法的序号,使用第num 个魔法:1.2..m
            	{
                    LL temp=p[num]-j;//算:伤害值-防御值
                    if(temp<=0)continue;//魔法不管用,继续使用下一个魔法
                    if(temp>=i)f[i][j]=min(f[i][j],k[num]);//如果第num魔法》=生命值i,那一招打死,最小能量为
                                       //自己和k[num],第num
                    else f[i][j]=min(f[i][j],f[i-temp][j]+k[num]);//否则看本身的小还是使用生命值减少+消耗能量
	            }
            }
        LL ans=0;//把n个幽灵全部打死:第一个幽灵f[a[1][b[1]]);第2个幽灵f[a[2][b[2]]);
	    for(int i=1;i<=n;i++)ans+=f[a[i]][b[i]];
       	cout<<ans<<endl;
	}
	return 0;
}


And else 在别处看到了这个题的另一个包装

实质上都是同一个问题,无区别

-------------------------------------------------------------------------------

恶魔城是一款风靡全亚洲的rpg游戏,游戏的设定是这样的:

 

你控制的主角叫贝尔蒙特,你需要打败恶魔城中的 n个幽灵才能获得最终的胜利,每个幽灵有生命值a[i]和魔法护盾防御值b[i]。贝尔蒙特一共有m种魔法攻击,第i种魔法需要消耗能量k[i],造成p[i]点伤害。

 

如果贝尔蒙特使用第i种魔法打在第j个幽灵身上,会使得第j个幽灵的生命值减少p[i]-b[j], 当然如果伤害小于魔法护盾,那么攻击就不会奏效。如果幽灵的生命值降为0或以下,那么就会被消灭。

每个魔法可以无限次使用,请问贝尔蒙特最少消耗多少能量,就可以消灭所有幽灵。

 

输入描述 Input Description

多组测试数据

每组数据第一行两个整数n,m(表示n个幽灵,m种魔法)。

接下来n行,每行两个整数a[i],b[i],分别表示幽灵的生命值和魔法护盾值。

接下来m行,每行两个整数k[i],p[i],分别表示第i种魔法消耗的能量值和造成的伤害值。

 

输出描述 Output Description

对于每组测试数据,输出最小的能量消耗,如果不能击败所有的幽灵,输出-1。

 

样例输入 Sample Input

1 2

3 5

7 10

6 8

1 2

3 5

10 7

8 6

 

样例输出 Sample Output

6

18

 

数据范围及提示 Data Size & Hint

40%数据:

1<=n<=100

1<=m<=100

1<=a[i]<=100

0<=b[i]<=10

0<=k[i]<=1000

0<=p[i]<=100

 

100%数据

1<=n<=100000

1<=m<=1000

1<=a[i]<=1000

0<=b[i]<=10

0<=k[i]<=100000

0<=p[i]<=1000

 

数据来源 Source

2017年暑假包河区初中组测试


本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr