首页 > 代码库 > HDU 2616 Kill the monster (暴力搜索 || 终极暴力全排列)
HDU 2616 Kill the monster (暴力搜索 || 终极暴力全排列)
题目链接:HDU 2616 Kill the monster
题意:有N个技能去打HP有M的怪兽,技能(A,M),技能伤害为A,当怪兽HP<=M时伤害为2*A。求打死怪兽(HP<=0)用的最少技能
方法一:将技能全排列,计算伤害,得到答案。
方法二:搜索,具体看代码。
全排列AC代码:
#include<stdio.h> #include<algorithm> using namespace std; struct node { int p,v; }; struct node st[30]; int main() { int n,d,i; int t[30]; int ans; while(scanf("%d %d",&n,&d)!=EOF) { for(i=0;i<n;i++) { scanf("%d %d",&st[i].p,&st[i].v);//p掉血,V double t[i]=i; } int sum; ans=100; do { sum=d; int count=0; for(i=0;i<n;i++) { if(sum<=st[t[i]].v) sum-=st[t[i]].p*2; else sum-=st[t[i]].p; count++; if(sum<=0) break; } if(sum<=0) ans=min(ans,count); }while(next_permutation(t,t+n)); if(ans==100) printf("-1\n"); else printf("%d\n",ans); } return 0; }
搜索AC代码:
#include<stdio.h> #include<algorithm> using namespace std; struct spell { int a,m; }; struct spell sp[20]; int n,ans,flag; bool vis[30]; void dfs(int p,int sum) { int i; if(sum<=0) { flag=1; ans=min(ans,p); return ; } for(i=0;i<n;i++) { if(!vis[i]) { vis[i]=true; if(sum<=sp[i].m) dfs(p+1,sum-sp[i].a*2); else dfs(p+1,sum-sp[i].a); vis[i]=false; } } } int main() { int i; int m; while(scanf("%d %d",&n,&m)!=EOF) { flag=0; memset(vis,false,sizeof vis); for(i=0;i<n;i++) scanf("%d %d",&sp[i].a,&sp[i].m); ans=n; dfs(0,m); if(flag) printf("%d\n",ans); else printf("-1\n"); } return 0; }
HDU 2616 Kill the monster (暴力搜索 || 终极暴力全排列)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。