http://acm.hdu.edu.cn/showproblem.php?pid=2616
Kill the monster
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 632 Accepted Submission(s): 443
Problem Description
There is a mountain near yifenfei’s hometown. On the mountain lived a big monster. As a hero in hometown, yifenfei wants to kill it.
Now we know yifenfei have n spells, and the monster have m HP, when HP <= 0 meaning monster be killed. Yifenfei’s spells have different effect if used in different time. now tell you each spells’s effects , expressed (A ,M). A show the spell can cost A HP to
monster in the common time. M show that when the monster’s HP <= M, using this spell can get double effect.
Now we know yifenfei have n spells, and the monster have m HP, when HP <= 0 meaning monster be killed. Yifenfei’s spells have different effect if used in different time. now tell you each spells’s effects , expressed (A ,M). A show the spell can cost A HP to
monster in the common time. M show that when the monster’s HP <= M, using this spell can get double effect.
Input
The input contains multiple test cases.
Each test case include, first two integers n, m (2<n<10, 1<m<10^7), express how many spells yifenfei has.
Next n line , each line express one spell. (Ai, Mi).(0<Ai,Mi<=m).
Each test case include, first two integers n, m (2<n<10, 1<m<10^7), express how many spells yifenfei has.
Next n line , each line express one spell. (Ai, Mi).(0<Ai,Mi<=m).
Output
For each test case output one integer that how many spells yifenfei should use at least. If yifenfei can not kill the monster output -1.
Sample Input
3 100 10 20 45 89 5 40 3 100 10 20 45 90 5 40 3 100 10 20 45 84 5 40
Sample Output
3 2 -1
这个我用深搜（Dfs）来搜的，我是模拟所有药剂使用顺序，找到药剂用量最少的一组。 把代码里面的注释恢复出来每次都是显示哪几个药剂被用了（用1表示），BOSS血量
还有多少。最后一个t显示杀死BOSS时药剂用量。
AC代码：
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define MAX 9999999
using namespace std;
struct Spells
{
int ai,mi; //伤害，加倍血量
int yn; //药剂是否被用
};
Spells sp[10];
int nu;
void Dfs(int n, int hpnow)
{
int now,i,t,j;
now = hpnow;
/*
for(j = 0; j < n; j++)
{
printf("%d ",sp[j].yn);
}
printf(" %d\n",now);
*/
if(now > 0)
{
for(i = 0; i < n; i++) //从第一瓶药剂开始搜索
{
if(sp[i].yn == 0) //判断是否用了此药剂
{
sp[i].yn = 1; //此药剂标记以用
if(now <= sp[i].mi) //判断血量时否满足双倍伤害
{
Dfs(n,now-2*sp[i].ai);
}
else
{
Dfs(n,now-sp[i].ai);
}
sp[i].yn = 0; //递归回来后重置此药剂没被有用
}
}
}
else
{
t = 0;
for(j = 0; j < n; j++)
{
if(sp[j].yn == 1)
{
t++;
}
}
// printf("t=%d\n",t);
if(t < nu)
{
nu = t;
}
}
}
int main()
{
int n,m,i,num;
while(scanf("%d%d",&n,&m)!=EOF)
{
num = 0;
nu = MAX;
for(i = 0; i < 10; i++)
{
sp[i].yn = 0;
}
for(i = 0; i < n; i++)
{
scanf("%d%d",&sp[i].ai,&sp[i].mi);
}
Dfs(n,m);
if(nu == MAX)
{
printf("-1\n");
}
else
{
printf("%d\n",nu);
}
}
return 0;
}