【題意】：Doraemon正在與m個敵人戰(zhàn)斗，Doraemon有兩種屬性HP和SP（經(jīng)常打機的朋友都知道是什么喇，HP是血量，SP是魔法量）。如果Doraemon的HP小于或等于0的話，那么就意味著戰(zhàn)斗失敗。HP和SP分別有一個上限LH、LS，每個回合中Doraemon和敵人輪流行動（Doraemon總是先行動），在每個回合中，Doraemon能選擇下列4種操作中的其中一種：
1.殺死一個敵人并使SP回復(fù)1點
2.恢復(fù)floor(0.2*LH）的血量
3.如果當前SP大于0，可以發(fā)動技能殺死D[SP]個敵人，并且SP清零
4.待機，其實就是什么都不做
每次在Doraemon行動完后，每個敵人可以消耗Doraemon一滴血。在每個回合的最后，Doraemon能夠恢復(fù)[當前敵人數(shù)%3]的SP。一開始Doraemon處于滿血，零SP的狀態(tài)，問Doraemon殺死所有敵人的最小回合數(shù)是多少？如果Doraemon不可能戰(zhàn)勝，請輸出“HELP!”。
【題解】：在比賽中看到這道題覺得是博弈，然后YY了一輪之后沒找到任何規(guī)律。后來發(fā)現(xiàn)這是一道搜索題，一個單純的bfs可解，而且bfs能滿足最小的回合數(shù)。這道題細節(jié)的地方比較多：
1.當前的HP和SP在任何時候都不能超過上限LH、LS
2.每回合結(jié)束前都要恢復(fù)[當前敵人數(shù)%3]的SP
3.每回合總是Doraemon先行動，然后輪到敵人行動
4.在使用完技能后SP要變成0，并且 [當前敵人數(shù) - D[SP]] 可能出現(xiàn)負數(shù)
5.[小優(yōu)化]第四種操作待機顯然是沒用的，如果選擇待機的話還不如選擇加血，這里可以剪掉。
【代碼】：
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 }