HDOJ搜索专题之Kill the monster

题目大意：英雄打怪，英雄有n个咒语，每个咒语能对怪造成一定的伤害，且只能使用一次，咒语使用的时机不同，伤害不同，具体表现为，当怪的体力小于某个特定值m时，伤害会加倍。每条咒语描述为(a,m)，表示怪的体力大于m时伤害为a，其他时间为2*a。问能不能将怪打死，若能输出最少使用的咒语数，否则输出"-1"。当怪的体力小于或等于0时即认为怪死了。

分析：要求最少的次数，很容易想到使用BFS，但用DFS的关键在于状态的判重，这题可以将已经使用的咒语列表构成状态，判重时不好处理。若使用迭代加深搜索IDS则不需判重，只是时间可能要多一点。因为n最大不超过10，即最大深度为10，肯定不会超时。

View Code

 1 #include <stdio.h>
 2 #include <stack>
 3 #define N 10
 4 using namespace std;
 5 typedef struct node
 6 {
 7   int hp,d;
 8   char vis[N];
 9 }node;
10 node cur,next;
11 stack<node> S;
12 int n,HP,a[N],m[N];
13 void idfs()
14 {
15   bool success=false;
16   int dmax=0,ans;
17   while(!success && dmax<=n)
18   {
19     dmax++;
20     cur.hp=HP;
21     cur.d=0;
22     for(int i=0;i<n;i++)  cur.vis[i]=0;
23     while(!S.empty()) S.pop();
24     S.push(cur);
25     while(!S.empty() && !success)
26     {
27       cur=S.top(),S.pop();
28       if(cur.hp<=0) success=true,ans=cur.d;
29       if(cur.d>dmax)  continue;
30       for(int i=0;!success && i<n;i++)
31       {
32         next=cur;
33         if(next.vis[i]) continue;
34         next.vis[i]=1;
35         next.d++;
36         if(next.hp<=m[i]) next.hp-=2*a[i];
37         else  next.hp-=a[i];
38         if(next.hp<=0)  success=true,ans=next.d;
39         else  S.push(next);
40       }
41     }
42   }
43   if(success) printf("%d\n",ans);
44   else  puts("-1");
45 }
46 int main()
47 {
48   while(~scanf("%d%d",&n,&HP))
49   {
50     for(int i=0;i<n;i++)  scanf("%d%d",&a[i],&m[i]);
51     idfs();
52   }
53   return 0;
54 }