【题意】：Doraemon正在与m个敌人战斗，Doraemon有两种属性HP和SP（经常打机的朋友都知道是什么喇，HP是血量，SP是魔法量）。如果Doraemon的HP小于或等于0的话，那么就意味着战斗失败。HP和SP分别有一个上限LH、LS，每个回合中Doraemon和敌人轮流行动（Doraemon总是先行动），在每个回合中，Doraemon能选择下列4种操作中的其中一种：
1.杀死一个敌人并使SP回复1点
2.恢复floor(0.2*LH）的血量
3.如果当前SP大于0，可以发动技能杀死D[SP]个敌人，并且SP清零
4.待机，其实就是什么都不做
每次在Doraemon行动完后，每个敌人可以消耗Doraemon一滴血。在每个回合的最后，Doraemon能够恢复[当前敌人数%3]的SP。一开始Doraemon处于满血，零SP的状态，问Doraemon杀死所有敌人的最小回合数是多少？如果Doraemon不可能战胜，请输出“HELP!”。
【题解】：在比赛中看到这道题觉得是博弈，然后YY了一轮之后没找到任何规律。后来发现这是一道搜索题，一个单纯的bfs可解，而且bfs能满足最小的回合数。这道题细节的地方比较多：
1.当前的HP和SP在任何时候都不能超过上限LH、LS
2.每回合结束前都要恢复[当前敌人数%3]的SP
3.每回合总是Doraemon先行动，然后轮到敌人行动
4.在使用完技能后SP要变成0，并且 [当前敌人数 - D[SP]] 可能出现负数
5.[小优化]第四种操作待机显然是没用的，如果选择待机的话还不如选择加血，这里可以剪掉。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "queue"
5 #include "cmath"
6 using namespace std;
7 #define MAX 105
8 int lh, ls, n;
9 int d[MAX];
10 int visit[255][105][45];
11 int add;
12
13 struct st {
14 int hp, sp, cnt;
15 void init(int a, int b, int c) {
16 if(a > lh) a = lh;
17 if(b > ls) b = ls;
18 hp = a, sp = b, cnt = c;
19 }
20 } start;
21
22 int bfs() {
23 queue<st> que;
24 que.push(start);
25 visit[start.hp][start.sp][start.cnt] = 1;
26 while (!que.empty()) {
27 st now = que.front(), next;
28 que.pop();
29 //第一种操作
30 next.init(now.hp - (now.cnt - 1), now.sp + 1 + (now.cnt - 1) % 3, (now.cnt - 1));
31 if (next.cnt <= 0) return visit[now.hp][now.sp][now.cnt];
32 if (next.hp > 0 && !visit[next.hp][next.sp][next.cnt]) {
33 visit[next.hp][next.sp][next.cnt] = visit[now.hp][now.sp][now.cnt] + 1;
34 que.push(next);
35 }
36 //第二种操作
37 next.init(now.hp + add - now.cnt, now.sp + now.cnt % 3, now.cnt);
38 if (next.hp > 0 && !visit[next.hp][next.sp][next.cnt]) {
39 visit[next.hp][next.sp][next.cnt] = visit[now.hp][now.sp][now.cnt] + 1;
40 que.push(next);
41 }
42 //第三种操作
43 if (now.sp > 0) {
44 if(now.cnt - d[now.sp] <= 0) return visit[now.hp][now.sp][now.cnt];
45 next.init(now.hp - (now.cnt - d[now.sp]), (now.cnt - d[now.sp]) % 3, (now.cnt - d[now.sp]));
46 if (next.hp > 0 && !visit[next.hp][next.sp][next.cnt]) {
47 visit[next.hp][next.sp][next.cnt] = visit[now.hp][now.sp][now.cnt] + 1;
48 que.push(next);
49 }
50 }
51 }
52 return -1;
53 }
54
55 void init() {
56 for (int i = 0; i < 255; i++)
57 for (int j = 0; j < 105; j++)
58 for (int k = 0; k < 45; k++)
59 visit[i][j][k] = 0;
60 add = (int) floor(0.2 * lh);
61 }
62
63 int main() {
64 while (~scanf("%d%d%d", &lh, &ls, &n)) {
65 for (int i = 1; i <= ls; i++) scanf("%d", &d[i]);
66 start.init(lh, 0, n);
67 init();
68 int ans = bfs();
69 if (ans == -1) printf("HELP!\n");
70 else printf("%d\n", ans);
71 }
72 return 0;
73 }