Luogu 5056 - 插头DP

这是一道插头 $DP$ 的模版题,简单介绍一下:

插头 $DP$ 主要用的是逐格递推的思想:假想有一条线划分了已解决的状态和未解决的状态,那么插头 $DP$ 就是对这条轮廓线进行 $DP$ 。

状态这么设计:$0$ 表示没有插头, $1$ 表示左插头, $2$ 表示右插头,发现是三进制状态,强行扩充成四进制状态。

由于状态数较多,又有冗余的存在,所以利用 $\operatorname{hash}​$ 来进行状态转移。

分别对转移进行解析:

  • 换行时的转移:

    结束时,轮廓线应当是一条直线,但由于上一轮转移时,为了方便尚未左移,所以需要将继承的所有状态左移。

  • 同行时的转移:

    对于当前 $DP$ 的格子,与轮廓线有两个接触面:左和上,分别记为 $w_1, w_2$,都可以用来放置插头。

    • 新建一个连通分量:

      当且仅当 $w_1 = w_2 = 0$ 时,才能新建连通分量。

    • 合并两个连通分量:

      • $w_1 = 0 \ \cap \ w_2 \neq 0​$

        上边有插头左边没有,向右转移时状态不发生改变;向下转移时状态改变。

      • $w_1 \neq 0 \ \cap \ w_2 = 0$

        左边有插头上边没有,向下转移时状态不发生改变;向右转移时状态改变。

      • $w_1 = w_2 = 1​$

        左上都有左插头,需要在右边找到一个最近的匹配的右插头,将其替换成左插头。

      • $w_1 = w_2 = 2​$

        左上都有右插头,需要在左边找到一个最近的匹配的左插头,将其替换成右插头。

    • 保持原来的连通分量:

      • $w_1 = 1 \ \cap \ w_2 = 2$

        已成回路,合并答案。

      • $w_1 = 2 \ \cap \ w_2 = 1$

        消除插头,继续匹配。

详情参见代码:

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
119
120
121
122
123
124
125
126
127
128
129
#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>

typedef long long lint;

#define MAXN 13
#define MAXS 2 << 24
#define MAXH 300000

using namespace std;

char s[MAXN << 1];
int mod = 299987;
int n, m;
int tx, ty;
int head[MAXH + 100], cnt[2], suffix[MAXS];
lint bit[MAXN + 1];
int a[MAXN + 10][MAXN + 10];
lint que[2][MAXS], val[2][MAXS];

void insert(int cur, lint state, lint sum) {
lint u = state % mod + 1;
for (int i = head[u]; i; i = suffix[i])
if (que[cur][i] == state) {
val[cur][i] += sum;
return ;
}
suffix[++cnt[cur]] = head[u];
head[u] = cnt[cur];
que[cur][cnt[cur]] = state;
val[cur][cnt[cur]] = sum;
}

void solve() {
int cur = 0;
lint ans = 0;
cnt[cur] = 1;
que[cur][1] = 0;
val[cur][1] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= cnt[cur]; ++j)
que[cur][j] <<= 2;
for (int j = 1; j <= m; ++j) {
memset(head, 0, sizeof(head));
int last = cur;
cur ^= 1;
cnt[cur] = 0;
for (int k = 1; k <= cnt[last]; ++k) {
lint state = que[last][k], amount = val[last][k];
int w1 = (state >> ((j - 1) << 1)) & 3, w2 = (state >> (j << 1)) & 3;
if (!a[i][j]) {
if (!w1 && !w2)
insert(cur, state, amount);
}
else if (!w1 && !w2) {
if (a[i + 1][j] && a[i][j + 1])
insert(cur, state ^ bit[j - 1] ^ (bit[j] << 1), amount);
}
else if (!w1 && w2) {
if (a[i][j + 1])
insert(cur, state, amount);
if (a[i + 1][j])
insert(cur, state ^ (bit[j] * w2) ^ (bit[j - 1] * w2), amount);
}
else if (w1 && !w2) {
if (a[i + 1][j])
insert(cur, state, amount);
if (a[i][j + 1])
insert(cur, state ^ (bit[j] * w1) ^ (bit[j - 1] * w1), amount);
}
else if (w1 == 1 && w2 == 1) {
int p = 1;
for (int l = j + 1; l <= m; ++l) {
if (((state >> (l << 1)) & 3) == 1)
++p;
if (((state >> (l << 1)) & 3) == 2)
--p;
if (!p) {
insert(cur, state ^ bit[j] ^ bit[j - 1] ^ bit[l] ^ (bit[l] << 1), amount);
break;
}
}
}
else if (w1 == 2 && w2 == 2) {
int p = 1;
for (int l = j - 2; l >= 0; --l) {
if (((state >> (l << 1)) & 3) == 1)
--p;
if (((state >> (l << 1)) & 3) == 2)
++p;
if (!p) {
insert(cur, state ^ (bit[j] << 1) ^ (bit[j - 1] << 1) ^ (bit[l] << 1) ^ bit[l], amount);
break;
}
}
}
else if (w1 == 2 && w2 == 1)
insert(cur, state ^ (bit[j - 1] << 1) ^ bit[j], amount);
else if (i == tx && j == ty)
ans += amount;
}
}
}
printf("%lld\n", ans);
}

void init() {
bit[0] = 1;
for (int i = 1; i < 13; ++i)
bit[i] = bit[i - 1] << 2;
}

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%s", s + 1);
for (int j = 1; j <= m; ++j) {
a[i][j] = s[j] == '.';
if (a[i][j]) {
tx = i;
ty = j;
}
}
}
init();
solve();
}