hdu 2616 Kill the monster（深搜）

題意：   有n種技能，每種技能只能用一次，怪物有m點血，問最少需要多少種技能可以把怪物殺死。   每種技能有兩個數值a和b，a表示攻擊力，b表示當怪物的血量小於等於b時，這種技能的攻擊力可以變為2a。   一點攻擊力可以殺掉怪物一點血。                 簡單深搜   加了一個剪枝後從 421 MS  瞬間 降到 93MS             code:      

#include <stdio.h>   
#include <string.h>   
struct node {  
    int M, spell;  
} a[11];  
int hp, n;  
int vis[11];  
int ans ;  
void dfs(int k, int HP) {  
    int i;  
    if(k>=ans) return ;  
    if(HP<=0) {  
        if(ans>k)  
            ans = k;  
        return;  
    }  
    for(i=1; i<=n; i++)  
        if(!vis[i]) {  
            vis[i] = 1;  
            HP<=a[i].M? dfs(k+1,HP-a[i].spell*2): dfs(k+1,HP-a[i].spell);  
            vis[i] = 0;  
        }  
  
}  
int main() {  
    int i;  
    while(~scanf("%d%d",&n,&hp)) {  
        for(i=1; i<=n; i++)  
            scanf("%d%d",&a[i].spell,&a[i].M);  
        ans = 12;  
        memset(vis,0,sizeof(vis));  
        dfs(0,hp);  
        if(ans !=12) printf("%d\n",ans);  
        else printf("-1\n");  
    }  
    return 0;  
}  

#include <stdio.h>
#include <string.h>
struct node {
    int M, spell;
} a[11];
int hp, n;
int vis[11];
int ans ;
void dfs(int k, int HP) {
    int i;
    if(k>=ans) return ;
    if(HP<=0) {
        if(ans>k)
            ans = k;
        return;
    }
    for(i=1; i<=n; i++)
        if(!vis[i]) {
            vis[i] = 1;
            HP<=a[i].M? dfs(k+1,HP-a[i].spell*2): dfs(k+1,HP-a[i].spell);
            vis[i] = 0;
        }

}
int main() {
    int i;
    while(~scanf("%d%d",&n,&hp)) {
        for(i=1; i<=n; i++)
            scanf("%d%d",&a[i].spell,&a[i].M);
        ans = 12;
        memset(vis,0,sizeof(vis));
        dfs(0,hp);
        if(ans !=12) printf("%d\n",ans);
        else printf("-1\n");
    }
    return 0;
}