分析：之前的一道模拟赛题是dp+dfs,这道题是dp+bfs.
我们设f[stu][i][j]为当前状态为stu,走到(i,j)的答案，考虑怎么设计stu,每个人的状态有3种：要么在原地，要么被背着，要么已经到了终点，那么用一个3进制数保存就可以了.
下面考虑怎么转移，直接递推肯定是不对的，dfs也不行，只能bfs了.我们每次可以选择不走，或者如果当前点有人就背起来，或者到了终点就放下所有人或者放下所有使速度变慢的人，写好几次转移就过了.
#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int inf = 0x7ffffff; int n, m, k, top, sx, sy, tx, ty, a[20][20], speed[30], f[60010][15][15], dx[] = { 1, -1, 0, 0 }, dy[] = { 0, 0, 1, -1 },flag[20]; char name[30][3],s[20][20]; struct node { int x, y, zhuangtai; }; int jisuan(int stu) { int tot = 0,sped = k; memset(flag, 0, sizeof(flag)); while (stu) { tot++; flag[tot] = stu % 3; stu /= 3; } for (int i = 1; i <= top; i++) if (flag[i] == 1) sped += speed[i]; if (sped < 1) sped = 1; return sped; } bool judge(int x, int y) { if (x >= 1 && x <= n && y >= 1 && y <= m) return true; return false; } int bei(int stu, int x, int y) { int cur, tot = 0; for (int i = 1; i <= top; i++) if (s[x][y] == name[i][0]) { cur = i; break; } memset(flag, 0, sizeof(flag)); while (stu) { tot++; flag[tot] = stu % 3; stu /= 3; } if (flag[cur]) return 0; flag[cur] = 1; for (int i = top; i >= 1; i--) stu = stu * 3 + flag[i]; return stu; } int fang1(int stu, int x, int y) { memset(flag, 0, sizeof(flag)); int tot = 0; while (stu) { tot++; flag[tot] = stu % 3; stu /= 3; } for (int i = 1; i <= top; i++) if (flag[i] == 1) flag[i] = 2; for (int i = top; i >= 1; i--) stu = stu * 3 + flag[i]; return stu; } int fang2(int stu, int x, int y) { int tot = 0; memset(flag, 0, sizeof(flag)); while (stu) { tot++; flag[tot] = stu % 3; stu /= 3; } for (int i = 1; i <= top; i++) if (flag[i] == 1 && speed[i] > 0) flag[i] = 2; for (int i = top; i >= 1; i--) stu = stu * 3 + flag[i]; return stu; } int qpow(int a, int b) { int res = 1; while (b) { if (b & 1) res *= a; a *= a; b >>= 1; } return res; } void bfs() { queue <node> q; node temp; temp.x = sx; temp.y = sy; temp.zhuangtai = 0; q.push(temp); while (!q.empty()) { node u = q.front(); q.pop(); int sudu = jisuan(u.zhuangtai),x = u.x,y = u.y; //printf("%d %d %d ", sudu, x, y); for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (judge(nx, ny)) { //只移动 if (s[nx][ny] != '#' && f[u.zhuangtai][nx][ny] > f[u.zhuangtai][x][y] + sudu) { f[u.zhuangtai][nx][ny] = f[u.zhuangtai][x][y] + sudu; node temp; temp.x = nx; temp.y = ny; temp.zhuangtai = u.zhuangtai; q.push(temp); } //背人 if (s[nx][ny] >= 'A' && s[nx][ny] <= 'Z') { int stu = bei(u.zhuangtai, nx, ny); if (f[stu][nx][ny] > f[u.zhuangtai][x][y] + sudu) { f[stu][nx][ny] = f[u.zhuangtai][x][y] + sudu; node temp; temp.zhuangtai = stu; temp.x = nx; temp.y = ny; q.push(temp); } } //放人 if (s[nx][ny] == 't') { int stu1 = fang1(u.zhuangtai, nx, ny); int stu2 = fang2(u.zhuangtai, nx, ny); if (f[stu1][nx][ny] > f[u.zhuangtai][x][y] + sudu) { f[stu1][nx][ny] = f[u.zhuangtai][x][y] + sudu; node temp; temp.zhuangtai = stu1; temp.x = nx; temp.y = ny; q.push(temp); } if (f[stu2][nx][ny] > f[u.zhuangtai][x][y] + sudu) { f[stu2][nx][ny] = f[u.zhuangtai][x][y] + sudu; node temp; temp.zhuangtai = stu2; temp.x = nx; temp.y = ny; q.push(temp); } } } } } } int main() { scanf("%d%d%d", &n, &m, &k); for (int i = 1; i <= n; i++) { scanf("%s", s[i] + 1); for (int j = 1; j <= m; j++) { if (s[i][j] == 's') { sx = i; sy = j; } else { if (s[i][j] == 't') { tx = i; ty = j; } else { if (s[i][j] >= 'A' && s[i][j] <= 'Z') top++; } } } } for (int i = 1; i <= top; i++) scanf("%s%d", name[i], &speed[i]); for (int i = 0; i <= 60000; i++) for (int j = 1; j <= 10; j++) for (int l = 1; l <= 10; l++) f[i][j][l] = inf; f[0][sx][sy] = 0; bfs(); printf("%d ", f[qpow(3, top) - 1][tx][ty]); return 0; }