[SCOI2012]喵星人的入侵
（思路大量参考 DP 带师 UM 的博客）
一个能直接把人干劝退的插头 DP 。。
Description
给定一个 \(n * m\) 图，有一个起点和终点和一些空地，你需要在空地上放置一些障碍和不超过 k 个炮台（均不可经过），使得：
-
起点和终点仍连通，可以存在多条路径；
-
每经过一个点（起终也算），答案加上该点八连通的炮台数，最大化答案（注：多条路径算答案最小的一条）。
\(\min(n,\ m) \leq 6,\ \max(n,\ m) \leq 20,\ 1\leq k \leq 15\)
Analysis
这个数据就很插头 DP 把，那就不去想其他的了。
那既然是要路径（不是回路），那自然一行的状态就直接 \(0\) 表示无插头， \(1\) 表示左插头， \(2\) 表示右插头， \(3\) 表示独立插头。
但是这样好像不太够，因为考虑到八连通下的贡献，需要知道附近几个点的状态，是路径，是炮台还是障碍。
所以需要一行状态形如（粉色那一列）：
对于打叉的点，记录的就是这些格子是路径，是炮台还是障碍（其他还有四个格子因为那个点还没遍历到，不考虑）。
（这两个都四进制就行，注：之后插头的叫状态 \(1\) ，格子种类的叫状态 \(2\) ）
还不够，因为有炮台的限制，所以还要加一个指炮台数量（最多 \(15\) 个所以二进制 \(4\) 位就够了）。
Solution
根据 Analysis 里说的，对于每个点，我们提取上一行状态 \(1\) 的左格 \(pr\) 和上格 \(pd\) ，状态 \(2\) 的左格 \(l\) ，左上格 \(ul\) ，上格 \(u\) ，右上格 \(ur\) 。
啊啊啊，** 大力分讨！！（推荐画图食用）
-
如果左，上都是路径但是都不是插头，说明这个地方不能再有路径接上去了，要么放障碍，要么放炮台。（也就这种情况是和状态 \(2\) 有关的）
-
这个点本来就是障碍点，那也就只有左，上均没有插头的时候能转移。
-
起点或终点（可以形象化成一个独立插头）
①. 均没有插头
直接新建独立插头。
②. 无插头 + 左插头（或左 + 无）
删除当前插头，并且把对应的右插头改成独立插头。
③. 无插头 + 右插头（或右 + 无）
删除当前插头，并且把对应的左插头改成独立插头。
④. 无插头 + 独立插头（或独立 + 无）
删除当前插头，没对应的插头，所以没了。 -
空地（插头种类不定，跟着之前的走就行）
①. 均没有插头
可以选择放障碍，放炮台，或者开一个新路径。
②. 仅有一个有插头
跟着插头走就行了。
③. 都是左插头
删除这两个插头，并且把上格插头对应的右插头变成左插头。
④. 都是右插头
删除这两个插头，并且把左格插头对应的左插头变成右插头。
⑤. 右插头 + 左插头
删除这两个插头，并且把对应的两个插头左右不变。
⑥. 左插头 + 右插头
不合法，这样就是闭合回路。
⑦. 左插头 + 独立插头（或独立 + 左）
删除这两个插头，并且把对应的右插头变成独立插头。
⑧. 右插头 + 独立插头（或独立 + 右）
删除这两个插头，并且把对应的左插头变成独立插头。
⑨. 独立插头 + 独立插头
直接删除，没什么能伸展出去的。
接下来，来想想怎么计算答案。
前面提到过，处理这个点的时候我们只知道周围四个点的状态。
那丢掉的四个点怎么办呢？在处理那四个点的时候自然就会算当前这个点了。正好，还不会算重。
因为相当于我们全部认定这个空地就是路径，那么他的贡献就是周围八个格子炮台数。转化一下也就是炮台的贡献就是周围八个格子空地数。
所以如果是炮台，就算已知的四个点里面空地数；
所以如果是空地，就算已知的四个点里面炮台数。
那不是还有多条路径算最小值的限制吗？
那你把答案最大的那条留下，剩下的直接全部用障碍填满，答案肯定不劣，况且这一定会在状态中出现，所以可以覆盖掉多条路径的影响。
那全部答案取合法里面的最大值就行了。
Code
Code
/* */ #include //#define int long long #define BT1 ((l == 1) + (ul == 1) + (u == 1) + (ur == 1)) #define BT3 ((l == 3) + (ul == 3) + (u == 3) + (ur == 3)) using namespace std; typedef long long ll; const int N = 24, zs = 299987; int n, m, K, a[N][N], p, las, fst[zs + 10], tot[2], ans, inc[N], pl[N]; struct BIT { int c0, c1, c2; bool operator == (const BIT &it) const { return (c0 == it.c0) && (c1 == it.c1) && (c2 == it.c2); } }; struct mdzz {int nxt, val[2]; BIT bt[2];} e[(1 << 24) + 10]; inline int read() { int s = 0, w = 1; char ch = getchar(); while (!isdigit(ch)) {if (ch == '-') w = -1; ch = getchar();} while (isdigit(ch)) {s = (s << 3) + (s << 1) + (ch ^ 48); ch = getchar();} return s * w; } inline void insert(int c0, int c1, int c2, int num) { int u = ((((1ll * c0 << 16) | c1) << 4) | c2) % zs + 1; for (int i = fst[u]; i; i = e[i].nxt) { if (e[i].bt[p] == (BIT) {c0, c1, c2}) { e[i].val[p] = max(e[i].val[p], num); return ; } } e[++tot[p]].nxt = fst[u]; e[tot[p]].bt[p] = (BIT) {c0, c1, c2}; e[tot[p]].val[p] = num; fst[u] = tot[p]; } int pr, pd, l, ul, u, ur, c0, c1, c2; inline int RT(int c0, int j, int pm) { int tot = 1, x = c0, lm; while (2333) { lm = (x >> pl[j]) & 3; if (lm == 1) ++tot; else if (lm == 2) --tot; if (!tot) return c0 ^ (lm << pl[j]) ^ (pm << pl[j]); ++j; } return 0; } inline int LT(int c0, int j, int pm) { int tot = 1, x = c0, lm; while (2333) { lm = (x >> pl[j]) & 3; if (lm == 2) ++tot; else if (lm == 1) --tot; if (!tot) return c0 ^ (lm << pl[j]) ^ (pm << pl[j]); --j; } return 0; } inline void Plugdp(int i, int j, BIT bit, int num) { //这里的c0是已经把左和上去掉的残缺状态 //这里的c1是已经把左上去掉的残缺状态 if ((!pr && l == 1) || (!pd && u == 1)) { if (pr || pd) return ; insert(c0, c1, c2, num); if (c2 < K && a[i][j] == 1) { insert(c0, c1 ^ (3 << pl[j]), c2 + 1, num + BT1); } } else if (a[i][j] == 2) { if (!pr && !pd) insert(c0, c1, c2, num); } else if (a[i][j] == 1) { if (!pr && !pd) { insert(c0, c1, c2, num); if (c2 < K) insert(c0, c1 ^ (3 << pl[j]), c2 + 1, num + BT1); insert(c0 ^ inc[j - 1] ^ (inc[j] << 1), c1 ^ inc[j], c2, num + BT3); } else if (!pr || !pd) { insert(c0 ^ ((pd | pr) << pl[j - 1]), c1 ^ inc[j], c2, num + BT3); insert(c0 ^ ((pd | pr) << pl[j]), c1 ^ inc[j], c2, num + BT3); } else if (pr == 1 && pd == 1) insert(RT(c0, j - 1, 1), c1 ^ inc[j], c2, num + BT3); else if (pr == 2 && pd == 2) insert(LT(c0, j - 1, 2), c1 ^ inc[j], c2, num + BT3); else if (pr == 2 && pd == 1) insert(c0, c1 ^ inc[j], c2, num + BT3); else if (pr == 1 && pd == 2) ; else if (pr == 1 && pd == 3) insert(RT(c0, j - 1, 3), c1 ^ inc[j], c2, num + BT3); else if (pr == 3 && pd == 1) insert(RT(c0, j - 1, 3), c1 ^ inc[j], c2, num + BT3); else if (pr == 2 && pd == 3) insert(LT(c0, j - 1, 3), c1 ^ inc[j], c2, num + BT3); else if (pr == 3 && pd == 2) insert(LT(c0, j - 1, 3), c1 ^ inc[j], c2, num + BT3); else if (pr == 3 && pd == 3) insert(c0, c1 ^ inc[j], c2, num + BT3); } else if (a[i][j] == 3 || a[i][j] == 4) { if (!pr && !pd) { insert(c0 ^ (3 << pl[j - 1]), c1 ^ inc[j], c2, num + BT3); insert(c0 ^ (3 << pl[j]), c1 ^ inc[j], c2, num + BT3); } else if (!pr && pd == 1) insert(RT(c0, j - 1, 3), c1 ^ inc[j], c2, num + BT3); else if (pr == 1 && !pd) insert(RT(c0, j - 1, 3), c1 ^ inc[j], c2, num + BT3); else if (!pr && pd == 2) insert(LT(c0, j - 1, 3), c1 ^ inc[j], c2, num + BT3); else if (pr == 2 && !pd) insert(LT(c0, j - 1, 3), c1 ^ inc[j], c2, num + BT3); else if (pr == 3 && !pd) insert(c0, c1 ^ inc[j], c2, num + BT3); else if (!pr && pd == 3) insert(c0, c1 ^ inc[j], c2, num + BT3); } } inline void plug() { tot[p] = 1; for (int i = 1; i <= n; ++i) { for (int j = 1, x; j <= tot[p]; ++j) { e[j].bt[p].c0 <<= 2; x = e[j].bt[p].c1; (e[j].bt[p].c1 ^= ((x >> pl[m + 1]) & 3) << pl[m + 1]) <<= 2; } for (int j = 1; j <= m; ++j) { memset(fst, 0, sizeof(fst)); swap(las, p); tot[p] = 0; for (int k = 1, num; k <= tot[las]; ++k) { BIT bit = e[k].bt[las]; num = e[k].val[las]; if (bit.c0 >= inc[m + 1]) continue; c0 = bit.c0; c1 = bit.c1; c2 = bit.c2; pr = (c0 >> pl[j - 1]) & 3; pd = (c0 >> pl[j]) & 3; l = (c1 >> pl[j - 1]) & 3; ul = (c1 >> pl[j]) & 3; u = (c1 >> pl[j + 1]) & 3; ur = (c1 >> pl[j + 2]) & 3; c0 ^= (pr << pl[j - 1]) ^ (pd << pl[j]); c1 ^= (ul << pl[j]); Plugdp(i, j, bit, num); } } } } inline int pdd(char ch) { if (ch == '.') return 1; if (ch == '#') return 2; if (ch == 'S') return 3; if (ch == 'T') return 4; if (ch == 'X') return 5; return 0; } int main() { n = read(); m = read(); K = read(); inc[0] = 1; las = 1; for (int i = 1; i <= 14; ++i) { inc[i] = inc[i - 1] << 2, pl[i] = i << 1; } if (n >= m) { char ch; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { ch = getchar(); while (!(a[i][j] = pdd(ch))) ch = getchar(); } } } else { swap(n, m); char ch; for (int j = 1; j <= m; ++j) { for (int i = 1; i <= n; ++i) { ch = getchar(); while (!(a[i][j] = pdd(ch))) ch = getchar(); } } } plug(); for (int i = 1; i <= tot[p]; ++i) { if (!e[i].bt[p].c0) ans = max(ans, e[i].val[p]); } printf(%d\n, ans); return 0; }