2010-1104

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

by liangjiaxing

'''题目描述：'''[[BR]]

小叮当打坏人。开始时，小叮当有lh的血量和0的技能值，现场有n个敌人。[[BR]]

他每回合有4种方法：[[BR]]

1.打掉一个敌人并增加一个技能值。[[BR]]

2.补lh*0.2血[[BR]]

3.用尽现有技能值s，打掉Ds个敌人[[BR]]

4.不动[[BR]]

小叮当打完之后，剩下 a 个敌人，小叮当扣 a 血，补充 a%3 的技能值。[[BR]]

问最少多少步打完所有敌人。[[BR]]


'''解题方法：'''[[BR]]

广度优先搜索，用结构体[[BR]]

{{{
struct p{
    int en, hp,sp,turn;
}p[1100000];
}}}
来表示状态，en表示敌人数，hp表示血量，sp表示技能值，turn表示回合数。[[BR]]

初始时，

[[BR]]
p[0].en=n;
[[BR]]
p[0].hp=lh;
[[BR]]
p[0].sp=0;
[[BR]]
p[0].turn=0;
[[BR]]
然后按照上述4种方案进行状态转移。

---

by pxhdg

实际上对于相同的敌人数与技能值，HP越多越好，因此只要记录HP最多的状态就可以了，只需要100*40＝4000个状态

---

by liangjiaxing

有道理

by liangjiaxing

题目描述：

小叮当打坏人。开始时，小叮当有lh的血量和0的技能值，现场有n个敌人。

他每回合有4种方法：

1.打掉一个敌人并增加一个技能值。

2.补lh*0.2血

3.用尽现有技能值s，打掉Ds个敌人

4.不动

小叮当打完之后，剩下 a 个敌人，小叮当扣 a 血，补充 a%3 的技能值。

问最少多少步打完所有敌人。

解题方法：

广度优先搜索，用结构体

struct p{
    int en, hp,sp,turn;
}p[1100000];

来表示状态，en表示敌人数，hp表示血量，sp表示技能值，turn表示回合数。

初始时，

p[0].en=n;

p[0].hp=lh;

p[0].sp=0;

p[0].turn=0;

然后按照上述4种方案进行状态转移。

---

by pxhdg

实际上对于相同的敌人数与技能值，HP越多越好，因此只要记录HP最多的状态就可以了，只需要100*40＝4000个状态

---

by liangjiaxing

有道理