2014
02-12

# Kill the monster

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.

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).

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).

3 100
10 20
45 89
5  40

3 100
10 20
45 90
5 40

3 100
10 20
45 84
5 40

3
2
-1

①简单bfs+状压(赤果果)

#include<stdio.h>
#include<queue>
using namespace std;

int n,m,data[10][2];
struct node
{
int spell,dist,hp;
};

int bfs(void)
{
node sn={0,0,m};
queue<node> Q;

Q.push(sn);
while( !Q.empty() )
{
node cur=Q.front();

Q.pop();
for(int i=0;i<n;i++)
{
if( cur.spell&(1<<i) )  continue;
node next={cur.spell|(1<<i),cur.dist+1,cur.hp-data[i][0]};

if( cur.hp<=data[i][1] )    next.hp-=data[i][0];
if( next.hp<=0 )    return next.dist;
Q.push(next);
}
}
return -1;
}

int main()
{
while( ~scanf("%d%d",&n,&m) )
{
for(int i=0;i<n;i++)
scanf("%d%d",&data[i][0],&data[i][1]);
printf("%d\n",bfs());
}
return 0;
}
/*
简单的bfs+状压
本来有个state[1024]数组，想剪掉一些肯定不是最优的情况
但发现有没有这个数组时间都一样，就舍掉了。
于是一个赤果果的bfs诞生了!!!
*/

②dfs枚举执行顺序 或 直接STL全排列(纯暴力)

#include<stdio.h>
#include<algorithm>
using namespace std;

int main()
{
int n,m,ans,data[10][2],p[10];

while( ~scanf("%d%d",&n,&m) )
{
for(int i=0;i<n;i++)    scanf("%d%d",&data[i][0],&data[i][1]);
for(int i=0;i<n;i++)    p[i]=i;
ans=m+1;
do
{
int hp=m;

for(int i=0;i<n;i++)
{
if( hp<=data[p[i]][1] )    hp-=2*data[p[i]][0];
else hp-=data[p[i]][0];
if( hp<=0 )
{
ans=min(ans,i+1);
break;
}
}
}while( next_permutation(p,p+n) );//STL
if( m+1==ans )  puts("-1");
else printf("%d\n",ans);
}
return 0;
}
/*
从ycl那里吸收来的想法，纯暴力枚举排列(即枚举执行顺序,也可以dfs写啦)
*/

1. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？