题解：P5056 【模板】插头 DP
Expert_Dream
·
·
题解
插头 DP。其核心思想是，利用状压维护轮廓线的状态进行 Dp 转移。
本文十分详细，富含丰富的图文解释，如果还是看不懂那么没救了。
定义
这是一个 8 \times 5 的网格，其中蓝线代表其中一条回路。我们暂且不考虑其 障碍。
记当前从左到右，从上往下枚举，枚举到的为图中绿色格子 (4,4)，则有：
-
轮廓线：为红色的一条 线，其作用是区分 已枚举 与 未枚举 部分的分割线。
-
插头：为了满足回路性质，一个格子有两个插头，对应的是四个方向其中的两个在回路图上的出度和入度。具体地，如格子 (2,2) 就有两个插头，分别为右插头和下插头。
状态设计
考虑对回路赋予方向。其中橙色的箭头代表着回路走到方向。
考虑用状态去记录 轮廓线 与 回路 相交的关系。
容易发现：
-
箭头向下：代表着 已枚举 的部分穿过 轮廓线 向 未枚举 的部分走。记为 1。
-
箭头向上：代表着 未枚举 的部分穿过 轮廓线 向 已枚举 的部分走。记为 2。
-
没有箭头：代表着 轮廓线 没有与回路有交点，即为 0。
那么我们就可以赋予上图中轮廓线的状态：(121002)_3。可以用三进制表示。
重点：状态记录的方式实际上是 括号序列。
即，状态中的 1 和 2 是满足 括号匹配 的。
若一个轮廓线上从左到右 a,b,c,d 四个点，若 (a,c) 是联通的，即从 a 往下走，然后从 c 又往上走回去。那么 (b,d) 肯定不能联通。可以理解为被 (a,c) 挡住，感性证明一下。
当然这个所谓的 方向 （即 1 和 2）实际上是相对的，而并非绝对的。他是在维护的过程中改变的，只要满足括号匹配原则即可。
状态转移
发现每一次转移只与上一次的轮廓线状态有关系。所以前两维可以优化掉。所以可以设计新状态 $dp_{now,s} ,now \in \{0,1\}$。
记当前枚举的 $(i,j)$ 点的左插头情况为 $x$，上插头情况为 $y$。如果插头存在则为 $1$ 否则为 $0$。
大体上可以分为 $7$ 中转移方式。
:::info[Type 1]{open}
若 $(i,j)$ 为障碍。则其必须在 $x=y=0$ 时才可以转移。
:::
:::info[Type 2]{open}
若 $x=y=0$ 且 $(i,j)$ 不是障碍。
此时 $(i,j)$ 的右插头和下插头必须存在。于是创建其右插头和下插头。
条件是 $(i+1,j)$ 和 $(i,j+1)$ 必须是非障碍格子。
所以在新的轮廓线（图中红色虚线）上，要加上 $1$ 和 $2$。（意义是这是一对括号，即一进一出）。而且 $1$ 要在 $2$ 前面，$1$ 对应的是左括号，$2$ 对应的右括号。
:::
:::info[Type 3]{open}
当 $x=1$ 且 $y=0$ 时，那么 $(i,j)$ 已经有一个插头了，所以需要考虑新建一个插头。新插头可以作为右插头或者下插头。分两种情况讨论。
判断条件依然同上是，新建下插头时 $(i+1,j)$ 必须非障碍。新建右插头时 $(i,j+1)$ 必须为非障碍。
当然，图中新轮廓线的 $1$ 和 $2$ 都可以，根据原先轮廓线。是要与原先轮廓线相同的。
:::
:::info[Type 4]{open}
当 $x = y = 1$，即条线合并了。所以两个 $1$ 类点会消失。不再需要记录他在轮廓线上的信息。所以根据括号匹配原则，后面会存在两个 $2$（右括号），于是将他们变成新的一对括号，修改左边的 $2$ 成为 $1$。
具体地，将 `(())` 变成了 `..()`。
:::
:::info[Type 5]{open}
当 $x=y=2$ 时，同理上一种情况可得，左边的第一个 $1$ 会变成 $2$。
:::
:::info[Type 6]{open}
当 $x=2$ 且 $y=1$ 时，合并了并不会对其他点造成影响，合并即可。
具体地，可以看作是 `()()` 到 `(..)`。
证明：由于括号匹配原则，$x$ 前必定有一个 $1$，$y$ 后必定 $2$，于是删掉 $x$ 和 $y$ 后括号匹配依然成立。
:::
:::info[Type7]{open}
当 $x=1$ 且 $y=2$ 时。
若当前不是最后一个非障碍点。那么他会是一个连通分量形成闭环，那么剩余未处理得非障碍点就会与目前的这个连通分量 **不连通**，违背了回路得要求。
于是此时当且仅当 $(i,j)$ 为最后一个处理的非障碍点，才能够合并。而合并了就结束了。所以在此时记录答案。
:::
至此，所有的转移结束。代码稍微有一些细节。
发现转移的状态并不会很多，所以我们可以用一个 map 储存即可。
:::success[AC code]
```cpp
int n,m;
int a[N][N],b[N];
pii lst;
unordered_map<int,int> dp[2];
void solve(){
cin >> n>>m;
For(i,1,n)For(j,1,m){
char c;cin >> c;
a[i][j] = (c == '.');
if(c=='.') lst={i,j};
}b[0]=1;For(i,1,12) b[i]=b[i-1] * 3;
dp[0][0] = 1; int now = 0;
int ans = 0;
For(i,1,n){
unordered_map<int,int>mp=dp[now];dp[now].clear();
for(auto it : mp) dp[now][it.fs*3] = it.sc;
For(j,1,m){
now=1-now; dp[now].clear();
for(auto it:dp[1-now]){
int sum = it.fs;
int count = it.sc;
int x = (sum / b[j-1]) % 3;
int y = (sum / b[j]) % 3;
if(!a[i][j]) {
if(!x && !y) dp[now][sum] += count;
}else if(!x&&!y){
if(a[i+1][j] && a[i][j+1]) dp[now][sum + b[j-1] + 2*(b[j])] += count;
}else if(!x&&y){
if(a[i+1][j]) dp[now][sum-y*b[j]+y*b[j-1]] += count;
if(a[i][j+1]) dp[now][sum] += count;
}else if(x&&!y){
if(a[i][j+1]) dp[now][sum-x*b[j-1]+x*b[j]] += count;
if(a[i+1][j]) dp[now][sum] += count;
}else if(x==1&&y==1){
int p=1;For(l,j+1,m){
if((sum/b[l])%3==1) p++;
else if((sum/b[l])%3==2) p--;
if(!p){
dp[now][sum-b[j-1]-b[j]-b[l]] += count; break;
}
}
}else if(x==2&&y==2){
int p=1;For_(l,j-2,0){
if((sum/b[l])%3==1) p--;
else if((sum/b[l])%3==2) p++;
if(!p){
dp[now][sum-2*b[j-1]-2*b[j]+b[l]] += count; break;
}
}
}else if(x==2&&y==1){
dp[now][sum-2*b[j-1]-b[j]]+=count;
}else if(i==lst.fs &&j == lst.sc) ans += count;
}
}
}cout<<ans<<endl;
}
```
:::
### 总结
插头 Dp 适合解决数据范围较小的网格含障碍的 **回路** 问题。利用了巧妙地轮廓线状态，将 $O(n\times m\times 2^{n\times m})$ 的时间复杂度优化到 $O(n\times m^2 \times 2^{m})$ 级别的。是状压一种非常人类智慧的做法。