杭電2616 Kill the monster(BFS過)(標識構造体解法)
Kill the monster
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1127 Accepted Submission(s): 788
Problem Description
There is a mountain near yifenfei’s hometown. On the mountain lived a big monster. As a hero in hometown, yifenfei wants to kill it.
Now we know yifenfei have n spells, and the monster have m HP, when HP <= 0 meaning monster be killed. Yifenfei’s spells have different effect if used in different time. now tell you each spells’s effects , expressed (A ,M). A show the spell can cost A HP to monster in the common time. M show that when the monster’s HP <= M, using this spell can get double effect.
Input
The input contains multiple test cases.
Each test case include, first two integers n, m (2Next n line , each line express one spell. (Ai, Mi).(0
Output
For each test case output one integer that how many spells yifenfei should use at least. If yifenfei can not kill the monster output -1.
Sample Input
Sample Output
この問題は実は暴力でも解ける.~しかしここではアルゴリズムを用いて効率を高めた.
题目爆一见リュックサックだと思っていたのですが(0-1)血の量をコントロールするのが难しいダメージが2倍と1倍になることがわかりました~そこでゆっくりとあきらめてしまいましたこの解法はやはり古い道を歩みました~
検索
実はこのテーマは深く探したほうが分かりやすいし、データも大きくないし、タイムアウトの問題には触れないとは限らない.
あ~でも私はやはり広く探して問題を解くのが好きです~
初期化について説明します.
次はbfsの本体です~
最後にACフルコードを貼り付けます.
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1127 Accepted Submission(s): 788
Problem Description
There is a mountain near yifenfei’s hometown. On the mountain lived a big monster. As a hero in hometown, yifenfei wants to kill it.
Now we know yifenfei have n spells, and the monster have m HP, when HP <= 0 meaning monster be killed. Yifenfei’s spells have different effect if used in different time. now tell you each spells’s effects , expressed (A ,M). A show the spell can cost A HP to monster in the common time. M show that when the monster’s HP <= M, using this spell can get double effect.
Input
The input contains multiple test cases.
Each test case include, first two integers n, m (2
Output
For each test case output one integer that how many spells yifenfei should use at least. If yifenfei can not kill the monster output -1.
Sample Input
3 100
10 20
45 89
5 40
3 100
10 20
45 90
5 40
3 100
10 20
45 84
5 40
Sample Output
3
2
-1
この問題は実は暴力でも解ける.~しかしここではアルゴリズムを用いて効率を高めた.
题目爆一见リュックサックだと思っていたのですが(0-1)血の量をコントロールするのが难しいダメージが2倍と1倍になることがわかりました~そこでゆっくりとあきらめてしまいましたこの解法はやはり古い道を歩みました~
検索
実はこのテーマは深く探したほうが分かりやすいし、データも大きくないし、タイムアウトの問題には触れないとは限らない.
あ~でも私はやはり広く探して問題を解くのが好きです~
初期化について説明します.
struct gongji
{
int spell[11],output,hp;//spell .output .hp .
}now,nex;
int a[11][2];//a[][0] a[][1] 次はbfsの本体です~
int bfs()
{
for(int i=0;i<11;i++)
{
now.spell[i]=0;
}// push ~ .
now.output=0;
now.hp=m;
queue<gongji>s;
s.push(now);
int caonima=0;
while(!s.empty())
{
now=s.front();
s.pop();
for(int i=0;i<n;i++)// .
{
if(now.spell[i]==1)continue;
nex=now;
nex.spell[i]=1;
nex.output=now.output+1;
if(now.hp<=a[i][1])nex.hp=now.hp-2*a[i][0];
else nex.hp=now.hp-a[i][0];
if(nex.hp<=0)return nex.output;
s.push(nex);
}
}
return -1;
}最後にACフルコードを貼り付けます.
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int n,m;
struct gongji
{
int spell[11],output,hp;
}now,nex;
int a[11][2];
int bfs()
{
for(int i=0;i<11;i++)
{
now.spell[i]=0;
}
now.output=0;
now.hp=m;
queue<gongji>s;
s.push(now);
int caonima=0;
while(!s.empty())
{
now=s.front();
s.pop();
for(int i=0;i<n;i++)
{
if(now.spell[i]==1)continue;
nex=now;
nex.spell[i]=1;
nex.output=now.output+1;
if(now.hp<=a[i][1])nex.hp=now.hp-2*a[i][0];
else nex.hp=now.hp-a[i][0];
if(nex.hp<=0)return nex.output;
s.push(nex);
}
}
return -1;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
for(int i=0;i<n;i++)
{
scanf("%d%d",&a[i][0],&a[i][1]);
}
printf("%d
",bfs());
}
}