插头DP 从入门到精通

· · 个人记录

0x10 插头 DP 是什么

插头 DP 就是状压 DP。不过是处理连通性问题的状压 DP。主要处理基于棋盘模型的，操作带有联通性的，方案计数或者价值最大问题。

回顾在棋盘模型上进行的那些普通状压 DP，如 炮兵阵地

可以发现他们的操作其实也是具有联通性的，但是这个连通性又什么特点?

这就导致了我们可以直接讨论出所有状态转移的方案。同时由于每个操作在一定程度上是独立的（我们无需考虑到每个攻击的格子的交叉情况，每个交叉的格子是否联通等），以至于可以用一个数来表示一行的状态，并且上下行之间的可变化小。所以这种 DP 可以做到逐行递推。

而插头 DP 的常见形式是这样的：

【模板】插头DP

以通常的思路来讲，我们用一个二进制数表示这一行格子上铺没铺线，但是考虑不下去了，因为无法在状态转移的时候确定和否合法，并且对于每一条线都可以有多种下一个铺法。并且，它是基于全局的联通，要求闭合回路。这种问题就要用到插头 DP 了。

0x20 普通棋盘形插头DP的思路

棋盘形插头 DP 通常有两种形式，本质差别不大，不过由于这是一篇面向没接触过插头 DP 的人的博客，我们分开讲一下。

0x21 路径形

典型的便是上文提到的模板，要求合法的一条路径。

插头 DP 题解或博客到这里大多是告诉你要设轮廓线，轮廓线的定义。我们来从本质讲讲为什么要设轮廓线。

这类联通性问题，单单考虑其中已经决策到的某一条路径（可能不是完整的），它的下一步应该怎么走的时候，就有多种走法，虽然这个是可以手讨出来的，但是在一整行上考虑的时候，由于不是最终状态，会导致有多条分裂的路径，如。

（上图借用于cdp论文。）

单单看蓝线上方那一段，他们就是多条路径，而我们按照普通状压枚举状态枚举的不是蓝线而是黄线。

在这行（状态）上存在的部分路径，既可以往下走，也可以往右走，也可以往左走，也可以终止。结合一行来看，转移是不可能的。所以这就是这类插头 DP 的第一个特点：逐格递推。

接下来考虑我们正在考虑某一格，一定是考虑完这一格继续考虑这一行下一格，这一格如何转移既能影响到下一行，又能影响到下一格（向下走，向右走），所以我们要维护一行的状态，一格一格推，这一行推过的格子的状态，这一格的状态，还没推过的格子的状态，三个组合起来形成了 轮廓线 这就是轮廓线。

看下面一个轮廓线：

手画了一个小时累死我了

黄色格子是我们正在决策的格子，你会发现由于它是一个格子，所以轮廓线要先向上走再向右走，所以轮廓线是要比列数多一位的， 并且在决策到第 i 位的时候，其实是 i 与 i + 1 位轮廓线来描述这一格的状态 。它是不断变化的。这是很容易搞混的一个点。

接下来怎么设计状态呢？

先不管最后形成一条回路，这道题的要求明显是路径不能交叉。我们要用轮廓线正确记录下合法的状态，有两种方法，最小表示法和括号表示法。

这里我们把每个格和其他格的联通情况看作插头，例如第四行第一列的格子有一个下插头和一个上插头，第一行第四列的格子有一个右插头和一个左插头。第七行第二列的格子有一个下插头和一个右插头。

最小表示法状态数大，不常用，所以在这里简单介绍下（才不是我没用过根本不会呢）

我自己理解的就是，将每个连通块当前表现在轮廓线上的插头编号为这个连通块最左边的那个插头是第几个出现的。

例如当前轮廓线：(1,2)(3,4)(5,9) 为相互联通的插头。注意，这里轮廓线某一位为 0 是这里没有 插头 而不是这里没有 路径 。那么这条轮廓线的状态就是 11223000003，其中，第 6 位和第 7 位一起表示第 6 格的状态。

先不讲转移了，有兴趣请自学（没用过）。

这种方法显然可以保证在转移的过程中保证不相交。原因见下面括号表示法。

最小表示法不优的原因在于它一个联通块要一个数来表示，当这个所以状态数会很大，括号表示法则用两个数 1,2 来表示连通块, 1 表示这个插头是他所在的连通块左边的插头，2 同上。由于我们是递推下来，下一行的状态之和上一行和这一行有关，所以我们的状态只要能正确表示出之前的某种合法方案即可。

为什么括号表示法是对的呢？

考虑从左到右 4 个插头 a, b, c, d。如果a, c 联通，a, b 不连通，则b, d 一定不连通。

（上图借用于cdp论文。）

证：在只考虑到轮廓线以上时，若 a，c联通， b，d 连通。 则 a, c 的路径一定与 b, d 的路径相交。

即插头之间有一个性质：两两匹配，不会交叉。正是括号匹配的性质，我们用0， 1, 2 表示状态，在转移的维护括号的性质，即可完美完成任务。

接下来状态怎么转移呢？考虑下面这张图：

这是可能的一种转移后的状态，考虑完黄色格子，绿线是转移完的轮廓线。为什么要把轮廓线这样变呢？再想想轮廓线的定义 （自创) ：

轮廓线是已决策完的格子和还未决策的格子之间的插头状态。

其实就是那条分界线上的状态，既然黄色格子决策完了，自然分界线就会变成这样。

由于我们只决策了一个格子，我们只需考虑有关这个格子的状态的变化，拿模板题分讨一下：

前情提要： 由于下面对初学者来说可能弄混，我提前声明，左插头是第 i 位状态，上插头是第 i + 1 位状态。转移后下插头是第 i 位状态，右插头是第 i + 1 位状态。

由于本题有障碍，预处理下，在转移的时候判断下一格是否是状态即可。

请忽略我的 Zip 函数。

我们判断完一格其实是结束一次操作，把判断完的状态存起来去递推下一个。

至此模板的主体部分以实现，接下来说一些其他部分。

下面是代码，本题主要滚动数组，注释很详细，可能有重复的地方。 （因为是我以前打的）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long

using namespace std;

const int Mod = 299987;
const int N = 14;
const int M = 2 << 24;

int n, m, ans;
int a[N][N];
char s;
int que[2][M], val[2][M]; // que是当前阶段hash对可行状态的映射数组, val是当前阶段hash映射数组所存的值， 即“f” 
int tw[N], cnt[2]; // tw是预处理の四进制数字，cnt为当前阶段可行の状态数（理解可以idx 
int ei, ej;
int now;
int last, num;

int Next[M], head[300000];
void Zip(int bit, int num){ // hash 压缩和连边  bit为当前状态, num 为这个状态的方案数 
    long long u = bit % Mod + 1; // 取head 
    for(int i = head[u]; i; i = Next[i]){
        if(que[now][i] == bit){
            val[now][i] += num;
            return;
        }
    }// 没有return就说明是新的点，建新边并且赋值 
    Next[++ cnt[now]] = head[u];
    head[u] = cnt[now];
    que[now][cnt[now]] = bit;
    val[now][cnt[now]] = num;
}

void dp(){
    cnt[now] = 1;
    val[now][1] = 1;
    que[now][1] = 0;
    for(int i = 1; i <= n; ++ i){ // 逐行推 
        for(int j = 1; j <= cnt[now]; ++ j) que[now][j] <<= 2; /*
        que是个队列，装的是上一步转移后的合法状态，由于我们是>>取插头，同时
        由上一条轮廓线的末状态（每个状态是进行一次转移的来的，可以看作剩下的部分不转移而直接到末状态）转移到这一条轮廓线的初状态，画图
        得知，上一个状态的最后一个插头一定不会有（不可能指向格外），这一个状态的第一个插头肯定不会存在(不可能由格外指进来)，即上一个状态
        一定是 00(最后一格储存在最高位） …… （两个二进制表示一个三进制数) 下一个状态还没开始转移的时候一定是  ……00 （第一格储存在第一位 
        这两个省略号表达的是相同的 ，因为还没发生转移。所以我们发现，由上一个转移的结束状态转为这个转移的初始状态，只需要 << 2
        */ 
        for(int j = 1; j <= m; ++ j){ // 逐格枚举 
            memset(head, 0, sizeof head); // 初始化hash链表 
            last = now; now ^= 1; // 滚动数组 
            cnt[now] = 0; // 滚动数组 
            for(int k = 1; k <= cnt[last]; ++ k){ //
                int bit = que[last][k], num = val[last][k]; // last阶段第k个状态，要求的是方案数，所以要继承last阶段第k个状态对应的方案数 
                int b1 = (bit >> ((j - 1) * 2)) % 4, b2 = (bit >> (j * 2)) % 4; // bit 为轮廓线状态，取出两个插头 
                if(!a[i][j]){ // 当前不可走
                    if(!b1 && !b2) Zip(bit, num); //有障碍，不增加括号序列 
                }
                else if(!b1 && !b2){ // 没有插头，新增个连通块。 
                    if(a[i + 1][j] && a[i][j + 1]) Zip(bit + tw[j - 1] + tw[j] * 2, num); //四进制下储存一个左括号一个右括号 
                }
                else if(!b1 && b2) {
                    if(a[i][j + 1]) Zip(bit, num);
                    if(a[i + 1][j]) Zip(bit - tw[j] * b2 + tw[j - 1] * b2, num); // b2 是右括号の四进制编号 
                }
                else if(b1 && !b2){
                    if(a[i + 1][j]) Zip(bit, num);
                    if(a[i][j + 1]) Zip(bit - tw[j - 1] * b1 + tw[j] * b1, num);
                } 
                else if(b1 == 1 && b2 == 1){ // 两个左括号 
                    int flag = 1;
                    for(int l = j + 1; l <= m; ++ l){
                        if((bit >> (l * 2)) % 4 == 1) flag ++;
                        if((bit >> (l * 2)) % 4 == 2) flag --;
                        if(!flag){ // 最左の右括号 
                            Zip(bit - tw[j] - tw[j - 1] - tw[l], num);
                            break; 
                        }
                    }
                }
                else if(b1 == 2 && b2 == 2){ //两个右括号 
                    int flag = 1;
                    for(int l = j - 2; l >= 0; -- l){
                        if((bit >> (l * 2)) % 4 == 1) flag --;
                        if((bit >> (l * 2)) % 4 == 2) flag ++;
                        if(!flag){ // 最右の左括号 
                            Zip(bit - tw[j] * 2 - tw[j - 1] * 2 + tw[l], num);
                            break; 
                        }
                    }
                }
                else{
                    if(b1 == 2 && b2 == 1) Zip(bit - tw[j - 1] * 2 - tw[j], num);
                    else if(i == ei && j == ej)  ans += num;
                }
            }
        }
    }
}

signed main(){
    scanf("%lld%lld", &n, &m);
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= m; ++ j){
            char ch = getchar();
            while(ch != '*' && ch != '.') ch = getchar(); 
            if(ch == '.'){
                a[i][j] = 1;
                ei = i; ej = j; // 结束节点 
            }
            else a[i][j] = 0;
        }
    tw[0] = 1; 
    for(int i = 1; i <= 13; ++ i) tw[i] = tw[i - 1] << 2; //每个下标是个四进制状态。 
    dp();
    printf("%lld\n", ans);
    return 0;
}

掌握了这道题，百分之 60 的插头 DP 你就都会了，不过是改改分讨，改改插头定义。这里给出几道练习题。

0x21 图形形

这种和上方差不多，但是介于我做的时候还是思考了段时间，这里简单说一下。

这种不同的地方在于它给你满足某些条件的图形， 用这个图形在网格上做操作。不同的地方是我们在分讨的时候某些条件的变化不同了，有时候插头的定义变化了，典型的是

P3272 [SCOI2011]地板

这道题要求 L 形砖来铺，那我们的转移就变化了，直走，或者转一下。

由于只能转一下，这里把插头设置为是否转过即可。

我写的题解

给出一道练习题

还有一道困难点的留在下面。

0x30 棋盘染色形插头DP的思路

见 cdp 论文所给出的题：

连通性这一条好整，按照插头 DP 的套路来就行，看向「不会有一个2 * 2 的子矩阵的 4 个格子的颜色全部相同」，即当我们决策到 a_{i.j} 的时候，a_{i-1, j-1} 会产生影响，所以我们在记录状态的时候要记录上那个那个格子的颜色。同时由于要产生联通的有两个颜色，所以还要分别记录上这一行的格子颜色。

所以我们要记录两个状态，和一个格子的颜色。

由于我没手打过（也不知道在哪打）

下面给出 cdp 的状态转移解释：

动态规划的状态为： 表示转移完 (i, j)，轮廓线上从左到右 n 个格子的染色情况为 S_0 (0 \le S_0 < 2n) ，连通性状态为 S_1 ，格子的颜色为 cp(0 或 1) 的方案总数。

状态转移： 枚举当前格子 (i, j) 的颜色，计算新的状态：S_0 和 cp 都很容易 O(1) 计算出来．考虑计算 S_1 ：轮廓线的变化相当于将记录 (i-1, j) 的连通性改成记录 (i, j) 的连通性．根据当前格子与上面的格子和左边的格子是否同色分四类情况讨论．应当注意的是如果 (i, j) 和 (i-1, j) 不同色，并且 (i-1, j) 在轮廓线上为一个单独的一个连通块，那么 (i-1, j) 以后都不可能与其他格子连通，即剩余的格子都必须染上与 (i-1, j) 相反的颜色，需要特殊判断．转移的时间复杂度为 O(n)。

下面一道结合了上面两种形式，可谓是毒瘤。

P2337 喵星人的入侵

本身打算写的但是这里都说完了也就剩个分类讨论不写了你们自己看其他题解吧（才不是我懒