http://acm.hdu.edu.cn/showproblem.php?pid=2616
题意:
有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; }