【模板】插头 dp 题解

【模板】插头 dp 题解

link
给定一个 $n \times m​$ 的方格,有些格子不能铺线,其他格子必须铺,求构成一个闭合回的方案数。
$ 2 \le n,m \le 12$

一个很显然的性质,因为是回路,所有要铺的格子都是一进一出两条线。

状态

考虑 dp,$f_{i, j, s}$ 当前决策到第 $i$ 行第 $j$ 个格子,状态为 $s$ 的方案数。

$s$ 的状态为当前决策的格子和未决策的格子之间的分界线,即轮廓线上有没有线穿过。

一个被引用不知多少次的好多题解都有的图

可以看到轮廓线的长度是 $m + 1$。

这里 $s$ 我知道的有两种存法,一种是最小表示法,一种是括号序列

最小表示法很直观,没有线就是 $0$,有线的话,一条线有两个线头,给这两个线头一个相同的标号。这样我们就得到一个状态,比如图中轮廓线状态可以表示为 12201。但这样一个状态可能会有多个表示,像图中 32203 也是它的一个表示,所以用最小表示法求出它的唯一状态。

但个人感觉括号序列更简洁易懂,所以关于最小表示法就不展开了。


一条线两个线头,一左一右;另外我们之前已经得到,所有格子都是一进一出,不会有两条线相交

聪明的你是不是已经发现了,这些性质与括号序列、括号匹配多么吻合。

确实,我们可以用 0 表示没线头,1 表示左括号,即左边的线头; 2 表示右边的线头。线不相交巧妙地保证了一个轮廓线状态只会有一个表示。

解决了状态,接下来就是转移了。

转移

我们计这个格子左边的状态为 $l$,$0$ 表示不连,$1$、$2$ 分别表示是左/右线头。同理计上面是否连为 $u$,右和下分别为 $r$、$d$。

可以发现,$l$ 所对应的就是 $s$ 中的第 $j$ 位,$u$ 就是第 $j + 1$ 位,我们的转移就是把 $l$、$u$ 转化为 $d$、$r$。

我们采用向后推的方式转移,也就是我们需要考虑在 $s$ 的状态下 $i$ 行 $j$ 列这个格子可以怎么连线。

Case 1

l = 0, u = 0

最简单的,左边上面都不连,要连两个线头的话只能是右和下都连了,即新开了一对括号。

r = 1, d = 2

Case 2

l = 0, u != 0

从上面可以连到右或下,并延续之前的括号状态。

r = u, d = 0r = 0, d = u

Case 3

l != 0, u = 0

与第二个情况类似。

r = l, d = 0r = 0, d = l


接下来的情况 $l$,$u$ 都不为零,所以 $r$,$d$ 都是零。

Case 4

l = 2, u = 1

两个区间的合并。

Case 5

l = 1, r = 1

同样是两个区间的合并,但不一样的是为了保证状态的正确性,我们要找到 $l$ 对应的右括号改为左括号。

Case 6

l = 2, r = 2

与 5 类似,找到 $u$ 对应的左括号改为右括号。

Case 7

l = 1, r = 2

为什么这个状态要放到最后讲呢,别忘了线不能相交,所以这个左右括号一定是对应、匹配的一对,这种情况出现代表着右一条线闭合了。这种情况只能在最后一个格子发生一次,此时更行答案。


至此转移也完成了!乌拉————

关于实现

实现中状态使用了四进制,并且实际上是倒着的,方便利用位运算简化代码。


会有很多的冗余状态,哈希或map就是在这里用的。


在转移时我们用到了三个对 $s$ 的操作:

  • 取出其中一位;
  • 修改其中一位;
  • 查找一个括号对应的另一个括号。

写成函数可以方便处理。


在每行最后是要特殊处理的!我们要改变一下轮廓线:

如图,要舍去第五位不为 $0$ 的状态,并将 $s$ 右移 $2$ 位(空出一个位置)。


最后一个格子应该是最后一个必须铺线的格子。


建议数组滚起来防止炸掉。


需要 long long

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <bits/stdc++.h>
using namespace std;

inline int read() {
int x = 0, f = 0; char c = 0;
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
return f ? -x : x;
}

#define N 14
#define int long long

int n, m, a[N][N], lst;
int res;

unordered_map<int, int> f, g;

inline int get(int st, int x) {
return ((st >> (x - 1 << 1)) & 3);
}
inline void chg(int &st, int x, int v) {
st ^= (st >> (x - 1 << 1) & 3) << (x - 1 << 1);
st ^= v << (x - 1 << 1);
}
inline int fid(int st, int x, int s = 0) {
if (get(st, x) == 1) {
for (x ++; s != 1; x ++) {
int t = st >> (x - 1 << 1) & 3;
if (t == 1) s --;
if (t == 2) s ++;
}
return x - 1;
} else {
for (x --; s != 1; x --) {
int t = st >> (x - 1 << 1) & 3;
if (t == 1) s ++;
if (t == 2) s --;
}
return x + 1;
}
}

signed main() {
for (int T = read(); T --;) {
memset(a, 0, sizeof a), f.clear(), g.clear(), res = 0;
n = read(), m = read();
int op = 0;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
a[i][j] = read();
op |= a[i][j];
}
}
if (!op) {
puts("1");
continue;
}

lst = n * m;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
if (a[i][j]) lst = i * (m - 1) + j;
}
}
f[0] = 1;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
for (auto k : f) {
int st = k.first, val = k.second;
int l = get(st, j), u = get(st, j + 1);
int r = a[i][j + 1], d = a[i + 1][j];

if (a[i][j] == 0) {
if (l == 0 && u == 0) g[st] += val;
continue;
}
if (l == 0 && u == 0) {
chg(st, j, 1), chg(st, j + 1, 2), g[st] += val;
}
if (l == 0 && u != 0) {
if (r) g[st] += val;
if (d) chg(st, j, u), chg(st, j + 1, 0), g[st] += val;
}
if (l != 0 && u == 0) {
if (d) g[st] += val;
if (r) chg(st, j + 1, l), chg(st, j, 0), g[st] += val;
}
if (l == 2 && u == 1) {
chg(st, j, 0), chg(st, j + 1, 0), g[st] += val;
}
if (l == 1 && u == 1) {
int t = fid(st, j + 1);
chg(st, j, 0), chg(st, j + 1, 0), chg(st, t, 1), g[st] += val;
}
if (l == 2 && u == 2) {
int t = fid(st, j);
chg(st, j, 0), chg(st, j + 1, 0), chg(st, t, 2), g[st] += val;
}
if (l == 1 && u == 2) {
chg(st, j, 0), chg(st, j + 1, 0);
if (i * (m - 1) + j == lst && st == 0) res += val;
else if (i * (m - 1) + j != lst) g[st] += val;
continue;
}
}
f.swap(g), g.clear();
}
for (auto k : f) {
if (k.first < (1 << (m << 1))) g[k.first << 2] = k.second;
}
f.swap(g), g.clear();
}

printf("%lld\n", res);
}
return 0;
}

等我一会多添点图


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!