hdu 2616【Kill the monster】

写的程序运行时间不给力~_~……

我用二进制表示状态做的……代码中解释……

代码如下：

 1 #include <iostream>
 2 using namespace std;
 3 
 4 struct spell
 5 {
 6     int ai,mi;
 7 }ss[12];
 8 int n,HP;
 9 int minn;
10 
11 void dfs(int x,int hp)
12 {
13     if(hp <= 0)//当hp值要小于等于0时，查看x中有多少个1，即用了多少个spell
14     {
15         int res = 0;
16         for(int i = 0;i < n;i ++)
17         {
18             if(x & (1 << i))
19                 res ++;
20         }
21         if(minn == -1 || minn > res)
22             minn = res;
23         return ;
24     }
25     if(x == (1 << n) - 1)//当全部用完了就要返回了
26         return;
27     for(int i = 0;i < n;i ++)
28     {
29         if(!(x & (1 << i)))//如果该spell没有用过就将该spell加进去用
30         {
31             int xx = x | (1 << i);
32             if(hp <= ss[i].mi)
33             {
34                 dfs(xx ,hp - ss[i].ai * 2);
35             }
36             else
37             {
38                 dfs(xx,hp - ss[i].ai);
39             }
40         }
41     }
42 }
43 
44 int main()
45 {
46     while(cin >> n >> HP)
47     {
48         for(int i = 0;i < n;i ++)
49         {
50             cin >> ss[i].ai >> ss[i].mi;
51         }
52 
53         minn = -1;
54         dfs(0,HP);
55         cout << minn << endl;
56     }
57 
58     return 0;
59 }