插头 DP

Hamburger999 · 2026-04-03 08:53:40 · 题解

1.什么是插头 DP？

一种基于轮廓线状态压缩的动态规划。

如果还是不太理解，我们可以看下面的一个例题：

【模板】插头 DP：

给出 n \times m 的方格，有些格子不能铺线，其它格子必须铺，形成一个闭合回路。问有多少种铺法？
2 \le n,m \le 12

下面的讲述都围绕着这个例题展开。

2.一些概念

下面设 (i,j) 为第 i 行第 j 列的格子，且编号均为 0-index。

2.1 轮廓线

看到上面的例题，显然会想到从上到下，从左到右去决策每个格子的填线方法。

如下图 2.1，是决策到格子 (2,1) 时棋盘的一种可能情况：

:::align{center}
图 2.1 :::

如图，绿色区域为已经决策的格子，蓝色区域为没有决策的格子。
注意到两个区域间有一条线（图中红线），这就是轮廓线。

2.2 插头

看图 2.2。

:::align{center}
图 2.2 :::

如图，格子 (0,2) 与下面的格子 (1,2) 有线连接，我们称 (0,2) 有一个下插头。
如图，格子 (1,2) 与上面的格子 (0,2) 有线连接，我们称 (1,2) 有一个上插头。

具体地，称一个格子的某个方向上有一个插头，当且仅当这个格子在该方向上的另一个格子有线连接。

3. 如何进行插头 DP？

3.1 如何存储状态？

我们观察下面的图 3.1：

:::align{center}
图 3.1 :::

可以看到，一个轮廓线上可能有 m 个下插头和 1 个右插头，共 m+1 个，我们从左到右存储每个格子的插头状态。这里将插头编号 0 \sim m。

只是存储每个位置是否有插头是不够的，我们需要存储关于这些插头的连通性信息。

观察到这些插头总是通过已经决策好的线两两配对的。且有一条重要性质：

轮廓线上不存在从左到右的 4 个插头 a,b,c,d，使得 a,c 配对，b,d 也配对。

请自行看图 3.2 感性理解 ~~，因为我不会证明~~。

:::align{center}
图 3.2 :::

注意到这个东西和括号序列很像。具体地，若将配对的插头中，靠左的记为 \texttt{(}，靠右的记为 \texttt{)}，而没有插头记为 \texttt{*}，则整个状态可表示为合法括号序列。

可以看图 3.3，其中记为 \texttt{(} 的插头染为了黄色，记为 \texttt{)} 的插头染为了绿色，下面图对应的状态为 \texttt{(()*)}。

:::info[另一种状态编码的方法] 直接存储每个插头所在连通块编号，没有插头就是 0。
这样的编号方式很多，如上面的状态可以是 12201 或 21102。我们取字典序最小的那个。
这个编码法叫做“最小表示法”。一些题目有用。 :::

:::align{center}
图 3.3 :::

实际存储时我们将 \texttt{*()} 三个字符分别看作 0,1,2，上面的状态可以看作三进制数 (11202)_3。但是由于位运算方便快速，而三进制还要进制转换，所以使用四进制数。

3.2 如何转移？

按照一开始说的，我们从上到下，从左到右去决策每个格子的填线方法，并转移到新的轮廓线状态。

如下图 3.4 是决策 (2,2) 填法时候的一种情况：

:::align{center}
图 3.4 :::

这个情况比较特殊，轮廓线状态不变。

实际的转移有很多情况，需要分类讨论。

下面设 p_1 为决策格右边的插头状态，p_2 为决策格上边的插头状态。

3.2.1 转移格子是障碍：

:::align{center} 图 3.5 :::

当 p_1=p_2=0 时直接转移，轮廓线不变。注意 p_1 \ne 0 或 p_2 \ne 0 时不要转移。

3.2.2 转移格子是空地，p_1=p_2=0：

:::align{center} 图 3.6 :::

增加一对插头，因为回路要铺满所有空地。

3.2.3 转移格子是空地，p_1=2,p_2=1：

:::align{center} 图 3.7 :::

连接插头，需要满足这个格子是最后一个空地，且连接后轮廓线上没有插头，这表示完成了回路，这一部分直接计入答案，不要转移。

3.2.4 转移格子是空地，p_1=p_2 \ne 0：

以 p_1=p_2=1 为例子：

:::align{center} 图 3.8 :::

两条路径连接了，消去这两个插头，并将与 p_2 匹配的插头 q_2 改为 1（与原来匹配 p_1 的插头 q_1 匹配。

当 p_1=p_2=2 时类似，具体地，消去这两个插头，并将与 p_1 匹配的插头 q_1 改为 2。

3.2.5 转移格子是空地，p_1=1,p_2=2：

:::align{center} 图 3.9 :::

设与 p_1 匹配的插头为 q_1，与 p_2 匹配的插头为 q_2。随着 p_1 与 p_2 的连接，q_1 与 q_2 也成为了一对匹配的插头。

3.2.6 转移格子是空地，[p_1=0]+[p_2=0]=1

:::align{center} 图 3.10 :::

延伸已有的插头即可，具体可延伸为上插头或右插头。

3.3 行之间的转移怎么办？

:::align{center}
图 3.11 :::

上面的分类讨论只能覆盖一行内的转移，我们考虑行间的转移。
显然只有最右边插头为 0 时可以转移，转移时将最右边的插头去掉并在最左边加入插头。

4. 一些实现细节

本题可以直接设 f_{i,j,S} 为考虑到 (i,j) 格子，轮廓线状态为 S 的时候的方案数，时间复杂度大概是 O(nmV) 的，V 是状态数（实测 m=12 时候 V=41835），转移参考上面。

但是直接这样会 MLE。我们可以考虑滚动数组，并只存储合法括号序列对应的状态。这些状态直接 DFS 搜索出来即可。

其实这样无用状态（值为 0 的状态）仍然很多，可以使用哈希表存储所有有用的状态，但是我没写。

可以使用下面的代码获取一个数 x 在四进制下第 p 位（最低位为 0）：

inline int getp(int x,int p){return ((x>>(p<<1))&3);}

以及将四进制下第 p 位改为 w：

inline int setp(int x,int p,int w){return (x&~(3<<(p<<1))|(w<<(p<<1)));}

这些操作可以方便转移。

5. 上代码！

#include<bits/stdc++.h>
using namespace std;
const int V=42000; 
int n,m,c,ex,ey,mp[V]; long long f[V],tmp[V],ans; char g[13][13]; unordered_map<int,int> rm;
inline int getp(int x,int p){return((x>>(p<<1))&3);}
inline int setp(int x,int p,int w){return (x&~(3<<(p<<1))|(w<<(p<<1)));}
inline int findl(int x,int p){ int r=0;
    for(int i=p;i>=0;i--){
        if(getp(x,i)==1) ++r; if(getp(x,i)==2) --r;
        if(r==0) return i;
    } return -1;
}
inline int findr(int x,int p){ int r=0;
    for(int i=p;i<m;i++){
        if(getp(x,i)==1) ++r; if(getp(x,i)==2) --r;
        if(r==0) return i;
    } return -1;
}
void dfs(int state,int x,int y){
    if(x==m+2){if(y==0)mp[++c]=state,rm[state]=c;return;}
    dfs(state<<2,x+1,y),dfs((state<<2)+2,x+1,y+1);
    if(y>0) dfs((state<<2)+1,x+1,y-1);
}
void print(int t){for(int i=0;i<=m;i++) cout<<(getp(t,i)==0?"#":getp(t,i)==1?"(":")");}
int main(){
    cin>>n>>m,dfs(0,1,0),f[1]=1;
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
        {cin>>g[i][j];if(g[i][j]=='.')ex=i,ey=j;}
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            for(int k=1;k<=c;k++) if(f[k]){
                int t=mp[k],p1=getp(t,j),p2=getp(t,j+1);
                if(g[i][j]=='*') {if(p1==0&&p2==0) tmp[k]+=f[k];continue;}
                if(p1==0&&p2==0) tmp[rm[setp(setp(t,j,1),j+1,2)]]+=f[k];
                if(p1==1&&p2==2&&i==ex&&j==ey&&!setp(setp(t,j,0),j+1,0)) ans+=f[k];
                if(p1==2&&p2==1) tmp[rm[setp(setp(t,j,0),j+1,0)]]+=f[k];
                if(p1==1&&p2==1) tmp[rm[setp(setp(setp(t,findr(t,j+1),1),j,0),j+1,0)]]+=f[k];
                if(p1==2&&p2==2) tmp[rm[setp(setp(setp(t,findl(t,j),2),j,0),j+1,0)]]+=f[k];
                if((p1==0&&p2!=0)||(p1!=0&&p2==0)){
                    tmp[rm[setp(setp(t,j,0),j+1,p1|p2)]]+=f[k];
                    tmp[rm[setp(setp(t,j,p1|p2),j+1,0)]]+=f[k];
                }
            }
            for(int k=1;k<=c;k++) f[k]=tmp[k],tmp[k]=0;
        }
        for(int k=1;k<=c;k++) if(getp(mp[k],m)==0) tmp[rm[mp[k]<<2]]+=f[k];
        for(int k=1;k<=c;k++) f[k]=tmp[k],tmp[k]=0;
    } return cout<<ans<<endl,0;
}

其实想清楚了很好写。

6.其它的例题

6.1 [SCOI2011] 地板

这个题中，一个 L 形只有一个插头，所以不能括号序列了。

仍然设 dp_{i,j,S} 为考虑到 (i,j) 格子，轮廓线状态为 S 的时候的方案数。

这里规定轮廓线上的插头为与 L 形相交的地方，由于 L 形的性质是拐了一个弯，所以有 2 类：

插头对应的 L 形还没有拐弯，记作 1。
插头对应的 L 形已经拐弯了，记作 2。

一个位置没有插头记作 0，这样轮廓线状态 S 仍然可以用三进制数表示，如下图表示为 (2110002)_3：

:::align{center}
图 6.1 :::

然后就是喜闻乐见的大力分类讨论转移环节，仍然设 p_1,p_2 为决策格右边，上边的插头状态。

1. 转移格为障碍

:::align{center}
图 6.2 :::

若 p_1=p_2=0 时直接转移即可。

2. 转移格为空地，p_1=p_2=0

:::align{center} 图 6.3 :::

新增一个地板，可以将当前格子作为地板的端点或者拐弯点，具体地增加一个插头 1 或两个插头 2。

3. 转移格为空地，[p_1=0]+[p_2=0]=[p_1=2]+[p_2=2]=1

:::align{center}
图 6.4 :::

延伸地板或将当前格子作为地板端点。

4. 转移格为空地，[p_1=0]+[p_2=0]=[p_1=1]+[p_2=1]=1

:::align{center}
图 6.6 :::

延伸地板或将当前格子作为地板拐弯点。

5. 转移格为空地，p_1=p_2=1

:::align{center}
图 6.7 :::

在当前格子将它们连接成一条地板。

可以证明，其它情况均不能转移。

行之间的转移和上一道题目相同，时间复杂度为 O(rc3^c)（认为 r \ge c），注意 r < c 时将矩阵旋转 90\degree。

这个题的代码与上一道类似，就不放代码了。

这种没有两两匹配，独立存在的插头称为独立插头。有时候独立插头可以与匹配插头同时存在。考虑以下题目（这个题和【模板】插头 DP 相似却又不同）：

给出 n \times m 的方格，有些格子不能铺线，其它格子必须铺，形成一条路径。问有多少种铺法？

请自行思考本题解法。

6.2 P4262 [Code+#3] 白金元首与莫斯科

6.2.1 Mondriaan's Dream / 蒙德里安的梦想

这个题有正常的状压 DP 解法，时间复杂度为 O(n4^m)，我们先讲解这个题的插头 DP 解法。这个做法~~更不需要脑子，~~ 时间复杂度更优，为 O(nm2^m)。

仍然设 f_{i,j,S} 为考虑到 (i,j) 格子，轮廓线状态为 S 的时候的方案数。

依然是分类讨论转移环节，仍然设 $p_1,p_2$ 为决策格右边，上边的插头状态。 ##### 1. 这个位置是障碍 $p_1=p_2=0$ 时可以直接转移。 ##### 2. 这个位置是空地且 $p_1=p_2=0

在当前格子放一个新的矩形，方向为向右或者向下，体现为在轮廓线上加一个插头。

3. 这个位置是空地且 p_1+p_2=1

延伸并结束这个矩形，体现为在轮廓线上删一个插头。

显然 p_1=p_2=1 时无法转移。

考虑本题。直接求方案数是简单的，只是在 p_1=p_2=0 时可以不放矩形。

但是恶心的题目加上了一个位置变成障碍的限制。

考虑再设 g_{i,j,S} 表示，从下到上，从右到左填，考虑到 (i,j) 格子，轮廓线状态为 S 时的方案数。

:::align{center}
图 6.8 :::

计算 (i,j) 格子变为障碍的方案数时，考虑将两条轮廓线拼合，如图所示。

则这两条轮廓线需要满足：

在障碍位置周围（即棕线）不能有插头。
其它位置的插头两两匹配。

设这两条轮廓线的上的插头状态均为 S（显然状态都一样），则对 (i,j) 位置的答案产生 f_{i,j-1,S} \cdot g_{i,j+1,S} 的贡献。注意 j=0 与 j=m-1 时要特判。

预处理 f,g 的时间复杂度为 O(nm2^m)，处理一格的答案的时间复杂度为 O(2^m)，故这个算法时间复杂度为 O(nm2^m)。

6.3 P4262 [JLOI2009] 神秘的生物

这个题目有些特殊。虽然也有连通性，但是插头并没有两两配对，轮廓线上的连通性状态如何表示？

考虑在 3.1 小节提到的另一种状态编码方法，它不需要符合两两配对的性质，只需要将所在连通块相同的插头赋上相同数字即可。如下图 6.9：

:::align{center}
图 6.9 :::

注意到我们不需要存储右插头的状态（因为与它左边的下插头状态一样），于是状态可以用 m 位数字表示。

本题中 n \le 9，最多有 \left\lfloor \dfrac{9}{2} \right\rfloor=5 个连通块，加上空插头，要使用 6 进制数存储状态，仍然是为了位运算方便，使用 8 进制数。

转移有以下可能（p_1 为右插头，p_2 为下插头）：

6.3.1 p_1=p_2=0

可以新增连通块。如下图：

:::align{center}
图 6.10 :::

6.3.1 p_1=p_2 \ge 0 或者 [p_1>0]+[p_2>0]=1

可以延伸连通块。如下图：

:::align{center}
图 6.11 :::

6.3.2 p_1 \ge 0,p_2 \ge 0,p_1 \ne p_2

可以合并连通块。如下图：

:::align{center}
图 6.12 :::

此外，所有转移均可设转移格为空，除了一个例外：

:::align{center}
图 6.13 :::

如图，若设置转移格为空，则粉色连通块就被孤立了，此时还有橙色连通块，不符合“只有 1 个连通块”限制。若没有其它颜色的连通块，则可以设置为空，但需要将此时的情况直接统计进答案中，不要转移（因为后面可能产生新的连通块）。

若图中被绿色框框起来的格子属于粉色连通块，则转移格可以为空，因为粉色还没有被孤立（剩下的一个插头仍然可以让粉色连通块与其它的连通）。

注意转移过后可能不满足“最小表示法”的字典序最小性质，需要重新对连通块编号。

答案即为满足轮廓线上有 \le 1 个连通块的方案总分的最大值。

注意不能不选连通块（即所有格子分值为负数时取最大值输出）

7. 课后练习

Eat the Trees
麦当劳叔叔的难题
[SCOI2016] 围棋
[NOI2010] 旅行路线