题解 P5056 【【模板】插头dp】
（时间：2020年5月21日 17点58分）
UPD: 论如何气活一个退役选手
最近总是有人说这代码 WA=0 , 我只能说，嗯，有道理。
我当时直接从某个OJ的提交记录里把代码复制了过来，所以这个算法是对的，这点毫无疑问，但是输出格式在谷上会WA
代码我不想改了，保留它本来的样子吧。
果然有模板了，那可不能少了我这篇讲解啊
我就不信你理解不了一篇全是图的讲解
后面附赠两道例题练习，也有写好的题解
（本文首发于 「头插DP指北」 ，原博客阅读效果更佳，欢迎围观。）
本文概览
-
什么是插头DP
-
插头DP的大致思路
-
划分阶段
-
记录状态
-
转移状态
-
新建一个连通分量
-
合并两个连通分量
-
保持原来的连通分量
-
一个小优化
-
-
-
代码
-
练习题
插头DP的概念（据我不可靠考证）最早出现在08年CDQ的论文中，而此类题目早在04年前后就已经存在。
（下面假设聚聚们都会了状压DP……）
1.什么是插头DP
插头DP (PlugDP)，也就是一类基于连通性的状态压缩动态规划，是用状压DP处理联通问题的强劲武器。
常见的类型有棋盘插头DP和CDQ论文里的两个非棋盘上的模型。
常见的联通问题：多回路问题、路径问题、简单回路问题、广义路径问题、生成树问题
2.插头DP的大致思路
2.1 划分阶段
大家都知道了这是基于联通性的状压 DP ，所以本质上还是状压 DP 。
一般设
所以我们状压什么呢？轮廓线。
DP求解棋盘问题是逐格转移的。所以已经转移过的格子和没转移过的格子被一个折线分成了两半儿。这个折线就是轮廓线。
（@远航之曲 的简洁解释:已决策格子和未决策格子的分界线）
就这个蓝线（现在转移的格子是第3行第3个）。
插头又是什么呢？一个格子有四个插头，一个存在的插头表示在它代表的方向上能与相邻的格子连接（联通）。不存在就不能。
为什么要引入插头？要求一个回路，也就意味着最后所有的非障碍格子通过插头连接成了一个连通块，因此转移时需要记录格子的连通情况。
我们递推的时候就是依据轮廓线上的插头存在性，求出所有能转移到的合法状态。
显然回路问题中一个格子恰好有两个插头，一个是 “进来” 的一个是 “出去” 的。
2.2 记录状态
最小表示法：
所有的障碍格子标记为
……重复这个过程，直到所有的格子都标记完毕。
比如连通信息
（还有一种极不常用的最小表示法，即一个连通块内所有的格子都标记成该连通块最左边格子的列编号。）
括号表示法：
【性质】轮廓线上从左到右
“两两匹配”，“不会交叉”这样的性质，我们很容易联想到括号匹配。
将轮廓线上每一个连通分量中左边那个插头标记为左括号，右边那个插头标记为右括号，由于插头之间不会交叉，那么左括号一定可以与右括号一一对应，这样我们就可以使用
状态的编码：
对于最小表示法，编码最简单的方法就是表示成一个
如需大范围修改连通块标号，最好将状态
2.3 转移状态
首先，因为逐行递推要讨论的情况还是比较难处理的，除非要求解的问题特别适合这样做，要不然我们一般使用逐格递推，这样可以方便讨论情况。
一般来说轮廓线上有不少状态都是无用的，而且一般来说头插插头 DP 的状态数很多，所以我们使用一个技巧来加速，那就是，我们用一个线性数据结构（我愿意开一个/模拟一个 vector ）来存储状态，每次读取上一格的所有合法状态扩展，而不是xjb枚举状态来扩展。
然后，我们来研究一下怎么转移。我们看一种题型吧。
(其实就是这道题)
-
给你一个
m \times n 的棋盘，有的格子是障碍，问共有多少条回路使得经过每个非障碍格子恰好一次。 -
1.新建一个连通分量
这个情况只出现在转移位置的轮廓线上没有下插头和右插头。
如图。然后我们只有一种转移方式就是当前格做右插头和下插头。
括号表示法就是新建一对紧挨着的左右括号。最小表示法就直接解码重编一下。
2.合并两个连通分量
如果当前轮廓线上既有右插又有下插，那你只能当前格做左插和上插，要不然就不是回路了。
然后如果右插和下插联通，那这种情况只能是在最后一个非障碍格是合法的。
不连通的话，当然这样做会把他们变联通，看图：
括号表示法里就直接删一对括号，最小表示法还是解码重编。
3.保持原来的连通分量
当轮廓线上只有下插或者右插，就只能当前格做一个左插/上插来满足回路性质，剩下一个插头是随便安排的。
图：
括号表示法的话就把下插/右插对应的括号移到你加的插头上就行了。
最小表示法也类似，把下插/右插位置的记号移到你加的插头对应位置就行（因为是延续了一个连通分量）。
注意当从一行的最后一个格子转移到下一行的第一个格子的时候，轮廓线需要特殊处理。这个看代码最好解释了。
（还要多啰嗦一句，一般状态编码的左右和轮廓线的左右是反着对应的……也就是编码最右面一位是对应轮廓线最左面格子）
( 这样大概比较好写? )
一个小优化
有时候你转移的时候有可能从两个不同状态转移出同一个状态，这个时候我们用 hash 优化它就好了。 hash 表的实现用挂表法就行。
还有提取每个插头状态的时候我们可以预处理一个对应 bit 的数组，然后用上文提到的解码方式去解码。
然后我们就讨论完了插头DP的第一道入门题该怎么做。上代码。这里由于洛谷排版的原因，解释我压在代码下面了，一定要好好看。后面一堆图，我就不信你看不明白是怎么转移的（不过最好的方法是去博客看原文）
-
state是表示状态，dp表示方案数。这里用了滚动数组来优化空间（pre,cnt来滚动） -
bits是一个方便提取插头的数组。比如bits[3]=6，那提取第三个格子上面和左面的插头（分别叫做is_d和is_r）就是state>>bits[3-1]和state>>bits[3] -
我们存储状态是四进制，括号表示法。
1 表示( ，2 表示) 。 -
hash 表的内部实现你可以看到就是一个链表。(
struct hash_table) -
因为可能最后一格也有障碍，所以要记录一下最后一个无障碍格子(
endx,endy)
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<cstdlib>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define mo 590027
using namespace std;
int n,m,mapx[20][20]={0},endx,endy;
ll all_ans=0,dp[2][600000]={0};
int bits[28]={0};
int state[2][600000]={0},tots[2]={0};
int pre=1,cnt=0;
struct hash_table
{
int pre,to;
}idx[600000]={0};
int ptr[600000]={0},at=0;
//------------FUNCTIONS HERE------------------------
inline void readx(int& x)
{
x=0; int k=1; register char ch=0;
while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar(); }
x*=k;
}
inline void readit()
{
readx(n); readx(m);
char cht=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
cht=0; while (cht!='.' && cht!='*') cht=getchar();
if (cht=='.') { mapx[i][j]=1; endx=i; endy=j; }
}
}
inline void init_bits() { for (int i=1;i<=25;i++) bits[i]=(i<<1); }
inline void hah(int sta,ll val)
{
int key=sta%mo;
for (int prex=ptr[key];prex;prex=idx[prex].pre) if (state[cnt][idx[prex].to]==sta)
{
dp[cnt][idx[prex].to]+=val;
return;
}
tots[cnt]++;
state[cnt][tots[cnt]]=sta;
dp[cnt][tots[cnt]]=val;
idx[++at].pre=ptr[key];
idx[at].to=tots[cnt];
ptr[key]=at;
}
inline void DP()
{
tots[cnt]=1; dp[cnt][1]=1;
state[cnt][1]=0;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=tots[cnt];j++) state[cnt][j]<<=2;//!!!
for (int j=1;j<=m;j++)
{
at=0; memset(ptr,0,sizeof ptr);//clear hash_table
swap(pre,cnt);//rolling
tots[cnt]=0;//clear state counter
register int nowsta,is_d,is_r; register ll nowans;
for (int k=1;k<=tots[pre];k++)
{
nowsta=state[pre][k],nowans=dp[pre][k];//get previous state&answer
is_d=(nowsta>>bits[j])%4,is_r=(nowsta>>bits[j-1])%4;//get current plugs
if (!mapx[i][j])//case 0
{
if ((!is_d) && (!is_r)) hah(nowsta,nowans);
}
else if ((!is_d) && (!is_r))//case 1
{
if (mapx[i+1][j] && mapx[i][j+1])
hah(nowsta+(1<<bits[j-1])+2*(1<<bits[j]),nowans);
}
else if ((!is_d) && is_r)//case 2
{
if (mapx[i+1][j]) hah(nowsta,nowans);//go down
if (mapx[i][j+1]) hah(nowsta-is_r*(1<<bits[j-1])+is_r*(1<<bits[j]),nowans);//go right
}
else if (is_d && (!is_r))//case 3
{
if (mapx[i][j+1]) hah(nowsta,nowans);//go right
if (mapx[i+1][j]) hah(nowsta-is_d*(1<<bits[j])+is_d*(1<<bits[j-1]),nowans);//go down
}
else if (is_d==1 && is_r==1)//case 4
{
register int count=1;
for (int l=j+1;l<=m;l++)
{
if ((nowsta>>bits[l])%4==1) count++;
else if ((nowsta>>bits[l])%4==2) count--;
if (!count)
{
hah(nowsta-(1<<bits[l])-(1<<bits[j])-(1<<bits[j-1]),nowans);
break;
}
}
}
else if (is_d==2 && is_r==2)//case 5
{
register int count=1;
for (int l=j-2;l>=0;l--)
{
if ((nowsta>>bits[l])%4==1) count--;
else if ((nowsta>>bits[l])%4==2) count++;
if (!count)
{
hah(nowsta-2*(1<<bits[j])-2*(1<<bits[j-1])+(1<<bits[l]),nowans);
break;
}
}
}
else if (is_d==1 && is_r==2)//case 6
hah(nowsta-2*(1<<bits[j-1])-(1<<bits[j]),nowans);
else if (is_r==1 && is_d==2)//case 7
if (i==endx && j==endy) all_ans+=(ll)nowans;
}
}
}
}
int main()
{
readit(); init_bits();
DP();
printf("%I64d\n",all_ans);
return 0;
}-
case 0:有障碍。
-
case 1:
-
case 2:
-
case 3:
-
case 4:(要改插头)
-
case 5:(要改插头)
-
case 6:(要改插头)
-
case 7:形成一个回路。只有最后一个格子才能形成一个回路。
练习题：
P3886 [JLOI2009]神秘的生物
这里面的题解也是我写的，和这篇一样难懂的风格。（包括代码风格）
[Code+#3]白金元首与莫斯科
这个大概有官方题解，你们自己找找吧。
还有 CDQ 的练习题表也挺好 ( 画红圈的那个和神秘的生物是一道题 ) ：
( 好不容易做一次 OI 网文写手，球点个赞吧 ! )