博洋教育今日就業(yè)明星：李祖張就職福建福諾移動通信技術擔任java工程師

獨家揭秘明星背后鮮為人知的故事：福建工程學院計算機科學與技術專業(yè)，本科學歷。在博洋教育參加JAVA軟件項目實訓，該生學習態(tài)度端正，有比較好的學習心態(tài)，會主動請教老師同學。畢業(yè)后經(jīng)過就業(yè)部老師的推薦，現(xiàn)在成功入職福建福諾移動通信技術有限公司。

博洋教育熱線：

QQ:

聯(lián)系人：廖老師

地址：福州市鼓樓區(qū)銅盤路軟件園軟件管委會大樓3樓網(wǎng)址:

題意：

有n種技能，每種技能只能用一次，怪物有m點血，問最少需要多少種技能可以把怪物殺死。

每種技能有兩個數(shù)值a和b,a表示攻擊力，b表示當怪物的血量小于等于b時，這種技能的攻擊力可以變?yōu)?a.

一點攻擊力可以殺掉怪物一點血。

簡單深搜

加了一個剪枝后從421MS瞬間降到93MS

code:

#include

#include

structnode{

intM,spell;

}a[11];

inthp,n;

intvis[11];

intans;

voiddfs(intk,intHP){

inti;

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;

}

}

intmain(){

inti;

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);

elseprintf("-1\n");

}

return0;

}

#include

#include

structnode{

intM,spell;

}a[11];

inthp,n;

intvis[11];

intans;

voiddfs(intk,intHP){

inti;

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;

}

}

intmain(){

inti;

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);

elseprintf("-1\n");

}

return0;

}