首页 > 搜索 > BFS搜索 > hdu 2616 Kill the monster-BFS-[解题报告]C++
2014
02-12

hdu 2616 Kill the monster-BFS-[解题报告]C++

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写啦)
 */

 

解题转自:http://www.cnblogs.com/kiwi-bird/archive/2012/11/22/2783347.html


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

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的