题解

思路分析

这是一道 插头DP + BFS + 状态压缩 的高难度综合题。

问题建模

• 在 $n \times m$ 网格上放置 $K$ 个炮塔
• 炮塔攻击周围8个方向
• 喵星人从 $S$ 走最短路到 $T$
• 目标：最大化喵星人受到的最小伤害

核心思路

1. 插头DP维护路径

使用插头DP维护从 $S$ 到当前位置的所有可能路径状态。

状态定义：

• 路径的连通性（是否形成有效路径）
• 每个格子的插头状态

2. 炮塔覆盖计算

对于每个状态，计算如果在该状态放置炮塔：

• 统计路径上每个格子受到的攻击次数
• 取路径上的最小伤害

3. 状态转移

对于每个格子，枚举：

• 是否放置炮塔（受 $K$ 限制）
• 路径是否经过
• 更新伤害值

4. 哈希优化

由于状态数巨大，使用哈希表存储状态。

算法步骤

1. 初始化：

   • 标记起点 $S$ 和终点 $T$
   • 初始化DP数组

2. 逐格DP：

   • 按行优先遍历
   • 枚举炮塔放置
   • 更新路径状态

3. 计算伤害：

   • 对每个状态计算最小伤害
   • 取所有状态的最大值

4. 输出答案

复杂度分析

• 状态数：$O(C \cdot 4^M)$
• 时间复杂度：$O(N \cdot M \cdot K \cdot 4^M)$
• 空间复杂度：$O(4^M)$

由于 $N \leq 6$，$M \leq 20$，$K \leq 15$，需要精心优化。

#include <bits/stdc++.h>
using namespace std;

const int N = 21, M = 8, C = 16;
int n, m, c, a[N][M];
const int TOT = 2e5 + 5, P = 1e5 + 5;
int f[2][C][TOT], ans;
int b1[M], b2[M];
bool o; int g, cnt_lj3;

struct HXB {
	struct node {int s, nxt;} e[TOT];
	int tot, head[P];
	
	void clr() {
		tot = 0;
		memset(head, 0, sizeof(head));
		return;
	}
	
	int operator [] (int s) {
		int x = s % P;
		for (int i = head[x]; i; i = e[i].nxt) {
			if (e[i].s == s) {
				return i;
			}
		}
		e[++tot] = {s, head[x]}, head[x] = tot;
		return tot;
	}
	
	void roll() {
		for (int i = 1; i <= tot; i++) {
			e[i].s &= (1 << (m << 2)) - 1;
			e[i].s <<= 4;
		}
		return;
	}
} H[2][C];

void cal_b(int s) {
	for (int i = 1; i <= m + 1; i++) {
		int x = s & 15;
		b1[i] = (x >= 2) + (x >= 6) + (x >= 10);
		while (x >= 6) {
			x -= 4;
		}
		b2[i] = x;
		s >>= 4;
	}
	return;
}

int cal_s() {
	int s = 0, dy[4], dy_cnt = 0;
	dy[0] = 0, dy[1] = dy[2] = dy[3] = -1;
	for (int i = m + 1; i; i--) {
		if (dy[b1[i]] == -1) {
			dy[b1[i]] = ++dy_cnt;
		}
		int x = dy[b1[i]] ? b2[i] + 4 * (dy[b1[i]] - 1) : b2[i];
		s = s << 4 | x;
	}
	return s;
}

bool hvr(int b) {
	return b == 4 || b == 5;
}

bool hvd(int b) {
	return b == 3 || b == 5;
}

void upd(int x, int y, int i, int b1y, int b2y, int sh) {
	if (x == n && hvd(b2y) || y == m && hvr(b2y) || cnt_lj3 + (b2y > 1) == 4) {
		return;
	}
	b1[y] = b1y, b2[y] = b2y;
	int s = cal_s();
	f[o][i][H[o][i][s]] = max(f[o][i][H[o][i][s]], g + sh);
	return;
}

void print() {
	cout << "b1: ";
	for (int i = 1; i <= m + 1; i++) {
		cout << b1[i] << " ";
	}
	cout << "\n";
	cout << "b2: ";
	for (int i = 1; i <= m + 1; i++) {
		cout << b2[i] << " ";
	}
	cout << "\n";
	cout << "f: " << g << "\n\n";
	return;
}

void dp() {
	f[0][0][H[0][0][0]] = 0;
	o = 1;
	for (int x = 1; x <= n; x++) {
		for (int y = 1; y <= m; y++, o ^= 1) {
			for (int i = 0; i <= c; i++) {
				memset(f[o][i] + 1, 0, H[o][i].tot << 2);
				H[o][i].clr();
			}
			for (int i = 0; i <= c; i++) {
				for (int j = 1; j <= H[!o][i].tot; j++) {
					g = f[!o][i][j];
					int s = H[!o][i].e[j].s;
					cal_b(s);
					int t1 = b2[y - 1], t2 = b2[y], t3 = b2[y + 1], t4 = y != m ? b2[y + 2] : 0;
					cnt_lj3 = (t1 > 1) + (t2 > 1) + (t3 > 1);
					int cnt_lj = cnt_lj3 + (t4 > 1);
					int cnt_pt = (t1 == 1) + (t2 == 1) + (t3 == 1) + (t4 == 1);
					bool lt = hvr(t1), up = hvd(t3);
//					cout << x << " " << y << " " << i << "\n";
//					print();
					if (a[x][y] == 1) {
						if (!lt && !up) {
							upd(x, y, i, 0, 0, 0);
						}
					}
					else if (a[x][y] == 2) {
						if (lt && !up && t3 < 2) {
							upd(x, y, i, b1[y - 1], 2, cnt_pt);
						}
						else if (!lt && up && t1 < 2) {
							upd(x, y, i, b1[y + 1], 2, cnt_pt);
						}
						else if (!lt && !up && t1 < 2 && t3 < 2) {
							upd(x, y, i, 3, 3, cnt_pt);
							upd(x, y, i, 3, 4, cnt_pt);
						}
					}
					else if (lt && up) {
						if (b1[y - 1] != b1[y + 1]) {
							int b1y = b1[y - 1];
							for (int k = 1; k <= m + 1; k++) {
								if (b1[k] == b1y) {
									b1[k] = b1[y + 1];
								}
							}
							upd(x, y, i, b1[y + 1], 2, cnt_pt);
						}
					}
					else if (lt && !up) {
						if (t3 < 2) {
							upd(x, y, i, b1[y - 1], 3, cnt_pt);
							upd(x, y, i, b1[y - 1], 4, cnt_pt);
						}
					}
					else if (!lt && up) {
						if (t1 < 2) {
							upd(x, y, i, b1[y + 1], 3, cnt_pt);
							upd(x, y, i, b1[y + 1], 4, cnt_pt);
						}
					}
					else {
						if (t1 < 2 && t3 < 2) {
							upd(x, y, i, 3, 5, cnt_pt);
						}
						upd(x, y, i, 0, 0, 0);
						if (i != c) {
							upd(x, y, i + 1, 0, 1, cnt_lj);
						}
					}
				}
			}
		}
		for (int i = 0; i <= c; i++) {
			H[!o][i].roll();
		}
	}
	for (int i = 0; i <= c; i++) {
		for (int j = 0; j <= H[!o][i].tot; j++) {
			ans = max(ans, f[!o][i][j]);
		}
	}
	return;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m >> c;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int x = i, y = j;
			if (n < m) {
				x = j, y = i;
			}
			char ch; cin >> ch;
			if (ch == '#') {
				a[x][y] = 1;
			}
			else if (ch == 'S' || ch == 'T') {
				a[x][y] = 2;
			}
		}
	}
	if (n < m) {
		swap(n, m);
	}
	dp();
	cout << ans;
	return 0;
}
/*
直接记录格子的状态。
无需管联通情况，因为只要只在 s 和 t 单方向开始就一定是一条路径。
搜索状态数后空间还是大，只有开 vector。

假了。
由于要求一条路径，所以要维护联通情况避免回路。
只会用到路径是否有向右和向下的延申，状态可以简化一些。
*/

题解

将地图逐格扫描时的限制（必须保持 $S$ 与 $T$ 连通、炮塔数不超过 $K$）与代价统计揉到一起，最合适的工具是插头 DP。状态按行推进：对前若干行已经处理好的前缀，只关心当前行及其上一行的轮廓情况即可。

具体地，给每一列额外保留一个“插头”，用 4 bit 编码表示该列上端的连通块编号以及该列是否已经放置炮塔、是否被障碍封死、是否已经被炮塔覆盖。b1[i] 表示第 $i$ 列插头所属的连通块编号，b2[i] 表示这一列的格子当前的类型（空地、障碍、炮塔以及是否会对通过者造成伤害），整行的轮廓编码由哈希表保存。每转移一格，枚举：放置障碍、放置炮塔或留空通行，并相应更新插头信息以及累计“如果以后路径经过这里会受到的伤害”。当一格被声明为炮塔时，会同时在 8 个方向上标记受到炮塔攻击的格子；放置障碍则直接在插头中切断这条通路；留空格需要维护连通块的合并与拆分，使得地图最终仅保留一条从 $S$ 到 $T$ 的通路。

状态中还附带“已经放置的炮塔数量”，因此总的 DP 维度是 f[row parity][used turrets][state id]，使用滚动数组和哈希桶维护。枚举完所有格子之后，在恰好使用不超过 $K$ 个炮塔的所有状态里取最大值，即可得到在满足连通性的前提下喵星人必经路径上能造成的最大总伤害。

#include <bits/stdc++.h>
using namespace std;

const int N = 21, M = 8, C = 16;
int n, m, c, a[N][M];
const int TOT = 2e5 + 5, P = 1e5 + 5;
int f[2][C][TOT], ans;
int b1[M], b2[M];
bool o; int g, cnt_lj3;

struct HXB {
	struct node {int s, nxt;} e[TOT];
	int tot, head[P];
	
	void clr() {
		tot = 0;
		memset(head, 0, sizeof(head));
		return;
	}
	
	int operator [] (int s) {
		int x = s % P;
		for (int i = head[x]; i; i = e[i].nxt) {
			if (e[i].s == s) {
				return i;
			}
		}
		e[++tot] = {s, head[x]}, head[x] = tot;
		return tot;
	}
	
	void roll() {
		for (int i = 1; i <= tot; i++) {
			e[i].s &= (1 << (m << 2)) - 1;
			e[i].s <<= 4;
		}
		return;
	}
} H[2][C];

void cal_b(int s) {
	for (int i = 1; i <= m + 1; i++) {
		int x = s & 15;
		b1[i] = (x >= 2) + (x >= 6) + (x >= 10);
		while (x >= 6) {
			x -= 4;
		}
		b2[i] = x;
		s >>= 4;
	}
	return;
}

int cal_s() {
	int s = 0, dy[4], dy_cnt = 0;
	dy[0] = 0, dy[1] = dy[2] = dy[3] = -1;
	for (int i = m + 1; i; i--) {
		if (dy[b1[i]] == -1) {
			dy[b1[i]] = ++dy_cnt;
		}
		int x = dy[b1[i]] ? b2[i] + 4 * (dy[b1[i]] - 1) : b2[i];
		s = s << 4 | x;
	}
	return s;
}

bool hvr(int b) {
	return b == 4 || b == 5;
}

bool hvd(int b) {
	return b == 3 || b == 5;
}

void upd(int x, int y, int i, int b1y, int b2y, int sh) {
	if (x == n && hvd(b2y) || y == m && hvr(b2y) || cnt_lj3 + (b2y > 1) == 4) {
		return;
	}
	b1[y] = b1y, b2[y] = b2y;
	int s = cal_s();
	f[o][i][H[o][i][s]] = max(f[o][i][H[o][i][s]], g + sh);
	return;
}

void print() {
	cout << "b1: ";
	for (int i = 1; i <= m + 1; i++) {
		cout << b1[i] << " ";
	}
	cout << "\n";
	cout << "b2: ";
	for (int i = 1; i <= m + 1; i++) {
		cout << b2[i] << " ";
	}
	cout << "\n";
	cout << "f: " << g << "\n\n";
	return;
}

void dp() {
	f[0][0][H[0][0][0]] = 0;
	o = 1;
	for (int x = 1; x <= n; x++) {
		for (int y = 1; y <= m; y++, o ^= 1) {
			for (int i = 0; i <= c; i++) {
				memset(f[o][i] + 1, 0, H[o][i].tot << 2);
				H[o][i].clr();
			}
			for (int i = 0; i <= c; i++) {
				for (int j = 1; j <= H[!o][i].tot; j++) {
					g = f[!o][i][j];
					int s = H[!o][i].e[j].s;
					cal_b(s);
					int t1 = b2[y - 1], t2 = b2[y], t3 = b2[y + 1], t4 = y != m ? b2[y + 2] : 0;
					cnt_lj3 = (t1 > 1) + (t2 > 1) + (t3 > 1);
					int cnt_lj = cnt_lj3 + (t4 > 1);
					int cnt_pt = (t1 == 1) + (t2 == 1) + (t3 == 1) + (t4 == 1);
					bool lt = hvr(t1), up = hvd(t3);
//					cout << x << " " << y << " " << i << "\n";
//					print();
					if (a[x][y] == 1) {
						if (!lt && !up) {
							upd(x, y, i, 0, 0, 0);
						}
					}
					else if (a[x][y] == 2) {
						if (lt && !up && t3 < 2) {
							upd(x, y, i, b1[y - 1], 2, cnt_pt);
						}
						else if (!lt && up && t1 < 2) {
							upd(x, y, i, b1[y + 1], 2, cnt_pt);
						}
						else if (!lt && !up && t1 < 2 && t3 < 2) {
							upd(x, y, i, 3, 3, cnt_pt);
							upd(x, y, i, 3, 4, cnt_pt);
						}
					}
					else if (lt && up) {
						if (b1[y - 1] != b1[y + 1]) {
							int b1y = b1[y - 1];
							for (int k = 1; k <= m + 1; k++) {
								if (b1[k] == b1y) {
									b1[k] = b1[y + 1];
								}
							}
							upd(x, y, i, b1[y + 1], 2, cnt_pt);
						}
					}
					else if (lt && !up) {
						if (t3 < 2) {
							upd(x, y, i, b1[y - 1], 3, cnt_pt);
							upd(x, y, i, b1[y - 1], 4, cnt_pt);
						}
					}
					else if (!lt && up) {
						if (t1 < 2) {
							upd(x, y, i, b1[y + 1], 3, cnt_pt);
							upd(x, y, i, b1[y + 1], 4, cnt_pt);
						}
					}
					else {
						if (t1 < 2 && t3 < 2) {
							upd(x, y, i, 3, 5, cnt_pt);
						}
						upd(x, y, i, 0, 0, 0);
						if (i != c) {
							upd(x, y, i + 1, 0, 1, cnt_lj);
						}
					}
				}
			}
		}
		for (int i = 0; i <= c; i++) {
			H[!o][i].roll();
		}
	}
	for (int i = 0; i <= c; i++) {
		for (int j = 0; j <= H[!o][i].tot; j++) {
			ans = max(ans, f[!o][i][j]);
		}
	}
	return;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m >> c;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int x = i, y = j;
			if (n < m) {
				x = j, y = i;
			}
			char ch; cin >> ch;
			if (ch == '#') {
				a[x][y] = 1;
			}
			else if (ch == 'S' || ch == 'T') {
				a[x][y] = 2;
			}
		}
	}
	if (n < m) {
		swap(n, m);
	}
	dp();
	cout << ans;
	return 0;
}
/*
直接记录格子的状态。
无需管联通情况，因为只要只在 s 和 t 单方向开始就一定是一条路径。
搜索状态数后空间还是大，只有开 vector。

假了。
由于要求一条路径，所以要维护联通情况避免回路。
只会用到路径是否有向右和向下的延申，状态可以简化一些。
*/