插头dp
之前在讲状压dp时还没有了解过插头dp，但状压的最后一道例题已经和插头dp很像了，这节就来解决一个插头dp的入门问题。

插头dp学习之前需要掌握或了解的东西：状压dp，哈希表，状压用来压缩一些局面，但可能出现的情况很多导致状压后的数很大，这时候就可以使用哈希表来仅存放已出现的局面，避免开辟太大的数组。

插头dp有几个关键词，当关键词出现时可以向这方面考虑：超小数据范围，网格图，连通性。

还需要理解一些抽象的定义：

插头

一个格子以某种方式向另一个格子相连，相连的位置叫插头，具体的类似拼图的凹槽与凸出这就是一种插头。

轮廓线

我们选取一个格子（i，j）作为决策点时，图中黄线就是轮廓线



轮廓线可以记录影响当前决策格或以后决策格做决策的要素（插头状态）。
例题：URAL1519
题目大意:一个网格图中有若干障碍格子，求其他格子的哈密尔顿回路总数
题解

这道题的数据范围很小可以使用状态压缩，又要求连通性那就使用插头dp。

首先定义轮廓线设轮廓线的单位部分从左到右有a，b，c，d四个插头，我们发现如果a，c连通，那么b，d就不可能连通，这其实是一个括号匹配问题，于是我们可以进一步定义，如果a，b连通左边的a记为1，右边的b记为2。

这样每个轮廓线的单位部分就有了三种情况，三进制数不好运算我们可以使用四进制数记录。

16位的四进制数太大了我们需要一个方法减少一些空间使用，这就用到了哈希表通过哈希表我们可以只记录出现了的状态，其中大量的无意义的状态就不用储存了。

综上我们确定了我们的用于状态转移的状态$f(i,j,S)$其中S为轮廓线状态。
状态转移方程
mp数组是网格的状态，0为有障碍，1为无障碍。

每次转移我们需要将决策格的上，左边转移为下，右边。其中决策格的上，左边会影响到我们当前决策格的决策，为了方便我们将其记为b1，b2,设轮廓线为a0a1a2a3a4



1.当前决策格有障碍

那么只有这个格子没有连通的时候才是合法情况，转移后轮廓线状态不变。
if(mp[i][j]){if(!b1&&!b2) ins(zt,num);}

其中ins（）函数是向轮廓线状态zt的方案加上num（就是简化的 $dp[now][zt]+=dp[las][zt`]$）。

2.当前决策无障碍：

（1）b1，b2都为0

那么只有决策格只有一种情况如图



转移后ai-1=1，ai=2。
else if (!b1 && !b2)
	{if (mp[i + 1][j] && mp[i][j + 1]) ins(zt + bin[j - 1] + 2 * bin[j], num);}

这里即使不判断要连通的格子是不是有障碍，也可以正确给出答案，但是会额外在哈希表中创立许多无效方案，加大了时间复杂度与空间复杂度，所以这里选择在转移前多判断一下。

（2）b1与b2其中一个为0

b2=0时有两张情况，第一种交换ai-1与ai



第二种轮廓线不变


if(b1&&!b2){
	if(mp[i][j+1]){ins(zt-bit[j-1]*b1+bit[j]*b1,num);}
	if(mp[i+1][j]){ins(zt,num);}
}

b1=0时同理。
if(!b1&&b2){
	if(mp[i][j+1]){ins(zt-bit[j]*b2+bit[j-1]*b2,num);}
	if(mp[i+1][j]){ins(zt,num);}
}

（3）b1=b2

当b1=b2=1时，当b1与b2是不同的连线可以连线，但是b1与b2可能已经连上了，所以我们需要沿着轮廓线去寻找这条线是否已经连上了。（不是单纯沿轮廓线寻找一个为2的插头，因为中间可能还有更多没连上的线）



转移后ai-1，ai=0，要注意的是连线后要把左边的一个2插头改为1插头。
if(b1==1&&b2==1){
	int k=1;
	for(int t=j+1;t<=m;t++){
		if((zt>>(2*t)%4)==1)k++;
		if((zt>>(2*t)%4)==2)k--;
		if(!k){ins(zt-bit[j]-bit[j-1]-bit[t],num);break;}
	}
}

b1=b2=2时，同理。
if(b1==2&&b2==2){
	int k=1;
	for(int t=j-2;t>=0;t--){
		if((zt>>(2*t)%4==2)k++;
		if((zt>>(2*t)%4==1)k--;
		if(!k){ins(zt+bit[t]-bit[j]*2-bit[j-1]*2,num);break;}
	}
}

（4）b1=2，b2=1



这个转移比较容易
if(b1==2&&b2==1) ins(zt-bit[j]-bit[j-1]*2,num);

（5）b1=1，b2=2



这种情况一定要注意如果连线就提前形成一个回路，只有最后一个非障碍的格子才可以连起来，形成回路。
完整代码
#include<iostream>
using namespace std;
const int MAX = 3e5 + 5, Has = 3e5 - 11;
int n, m, e1, e2, las, now = 0;
long long ans;
int mp[15][15], bin[15], tot[2];
int h[MAX];

struct Hashtable//哈希表，a用来存轮廓线状态，js用来存方案数，next存放哈希冲突时下一个格子的坐标
{
	long long js[2];
	int a[2], next;
}has[MAX];

void ins(int zt, int num)
{
	int tmp = zt % Has + 1;
	for (int i = h[tmp]; i; i = has[i].next)
		if (has[i].a[now] = zt) { has[i].js[now] += num; return; }
	has[++tot[now]].next = h[tmp];
	h[tmp] = tot[now];
	has[tot[now]].js[now] = num;
	has[tot[now]].a[now] = zt;
}

void work()
{
	tot[now] = 1; has[1].a[now] = 0; has[1].js[now] = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= tot[now]; j++)has[j].a[now] <<= 2;//换行转移
		for (int j = 1; j <= m; j++)
		{
			las = now; now ^= 1;
			memset(h, 0, sizeof(h));
			tot[now] = 0;
			for (int k = 1; k <= tot[las]; k++)
			{
				int zt = has[k].a[las];
				long long num = has[k].js[las];
				int b1 = (zt >> (2 * (j - 1))) % 4, b2 = (zt >> (2 * j)) % 4;//提取决策格上的轮廓线
				if (!mp[i][j]) { if (!b1 && !b2)ins(zt, num); }
				else if (!b1 && !b2)
				{
					if (mp[i + 1][j] && mp[i][j + 1]) ins(zt + bin[j - 1] + 2 * bin[j], num);
				}
				else if (!b1&&b2) {
					if (mp[i][j + 1]) ins(zt, num);
					if (mp[i + 1][j]) ins(zt - bin[j] * b2 + bin[j - 1] * b2, num);
				}
				else if (b1 && !b2) {
					if (mp[i][j + 1]) ins(zt - bin[j - 1] * b1 + bin[j] * b1, num);
					if (mp[i + 1][j]) ins(zt, num);
				}
				else if (b1 == 1 && b2 == 1) {
					int kl = 1;
					for (int t = j + 1; t <= m; ++t) {
						if ((zt >> (t * 2)) % 4 == 1) ++kl;
						if ((zt >> (t * 2)) % 4 == 2) --kl;
						if (!kl) { ins(zt - bin[j] - bin[j - 1] - bin[t], num); break; }
					}
				}
				else if (b1 == 2 && b2 == 2) {
					int kl = 1;
					for (int t = j - 2; t >= 0; --t) {
						if ((zt >> (t * 2)) % 4 == 1) --kl;
						if ((zt >> (t * 2)) % 4 == 2) ++kl;
						if (!kl) { ins(zt + bin[t] - 2 * bin[j] - 2 * bin[j - 1], num); break; }
					}
				}
				else if (b1 == 2 && b2 == 1) ins(zt - 2 * bin[j - 1] - bin[j], num);
				else if (i == e1 && j == e2) ans += num;
			}
		}
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			char ch;
			ch = getchar();
			while (ch != '*'&&ch != '.')ch = getchar();
			if (ch == '.')
			{
				mp[i][j] = 1;
				e1 = i;
				e2 = j;
			}
		}
	}
	bin[0] = 1;
	for (int i = 1; i <= 12; i++)bin[i] = bin[i - 1] << 2;
	work();
	cout << ans << endl;
	system("pause");
	return 0;
}

本题除了转移方程的策略选择，还有哈希表的构造，本题哈希需要存储轮廓线状态，方案数两种数据各两次，这里使用了一个结构体包装，如果拆成单个数组也可以通过相同的索引调用数据。

本题的哈希表处理哈希冲突的方式是链表法，将冲突的元素通过next连接到了链表头。

这里的代码我发现与储存图的链式向前星相似（都是用数组写链表）可以结合理解。

还有本题用到了滚动数组减少空间，之前状压dp也讲到了。

    
先%%学长优秀博客：%%
并借用他的定义：
插头DP主要用来处理一系列基于连通性状态压缩的动态规划问题，处理的具体问题有很多种，并且一般数据规模较小。
由于棋盘有很特殊的结构，使得它可以与“连通性”有很强的联系，因此插头DP最常见的应用要数在棋盘模型上的应用了。
直接上题
一、HDU1693 Eat the Trees
题目大意：给出一张n*m有障碍的棋盘，要求用任意条回路遍历整个棋盘，不能经过障碍格子，要求统计不同的行走方案数。
 
Sample Input
 

2
6 3
1 1 1
1 0 1
1 1 1
1 1 1
1 0 1
1 1 1
2 4
1 1 1 1
1 1 1 1

 
Sample Output
 
Case 1: There are 3 ways to eat the trees.
 
Case 2: There are 2 ways to eat the trees.
 
 

 
具体过程请参考学长博客，我就不搬了（没素质），上解释代码
重点看Execution函数的分情况讨论的实现 （Execution中判断x==n，y==m的状况可以不写正常转移）


 1 ^:不同则1,相同则0
 2 &:全1则1,有0则0
 3 #include <cstdio>
 4 #include<iostream>
 5 #include <cstring>
 6 using namespace std;
 7 typedef long long LL;
 8 int n,m,bin[20],mp[13][13];
 9 LL f[13][13][(1<<12)+10];//f[i][j][k]表示转移完第i行第j列插头状态为k时的方案数
10 inline void Execution(int x,int y)
11 {
12     int plug1=bin[y-1],plug2=bin[y];//分类bin[y-1]为左插头，bin[y]为上插头
13     if(x==n&&y==m)//最后状态只走0即可
14     {
15         if(mp[x][y])//!障碍且j状态没有插头，^后为有两个插头，及由y-1有两个插头转移
16             f[x][y][0]+=f[x][y-1][plug1^plug2];
17         else//障碍并且转移后保证没有插头及一定合法
18             f[x][y][0]=f[x][y-1][0];//所以没有插头连向它才合法转移
19         return;
20     }
21     for(int j=0;j<bin[m+1];j++)//枚举状态（此时第m+1个插头可以为1）
22         if(mp[x][y])//!障碍
23         {
24             f[x][y][j]+=f[x][y-1][j^plug1^plug2];
25             //plug1^plug2的第y-1，y这两位为1（从0开始）
26             //如果j状态有两个插头，^后为没有插头，及由y-1的没有插头转移
27             //如果j状态没有插头，^后为有两个插头，及由y-1有两个插头转移
28             //如果j状态有一个，^10变01，及由y-1有一个插头且不转向转移来
29             //10变10没法实现，只能排除00/11的情况，直接变
30             if(((j>>(y-1))&1)==((j>>(y))&1)) continue;//都为没插头或都有
31             f[x][y][j]+=f[x][y-1][j];//10变10，及由y-1有一个插头转向转移
32         }
33         else//障碍
34         {
35             if(!(j&plug1)&&!(j&plug2))//y-1处理完后该格没有左插头和上插头，同((!((j>>(y-1))&1))&&(!((j>>y)&1)))
36                 f[x][y][j]=f[x][y-1][j];//及没有插头连向它才合法转移
37             else f[x][y][j]=0;//否则方案数为0
38         }
39 }
40 int main()
41 {
42     int t;
43     scanf("%d",&t);
44     bin[0]=1;
45     for(int i=1;i<=15;i++) //2^最大方案数
46         bin[i]=bin[i-1]<<1;
47     //cout<<bin[8]<<endl;
48     for(int u=1;u<=t;u++)
49     {
50         scanf("%d%d",&n,&m);
51         for(int i=1;i<=n;i++)
52             for(int j=1;j<=m;j++)
53                 scanf("%d",&mp[i][j]);
54         memset(f,0,sizeof(f));
55         f[1][0][0]=1;//*************初始化第0格*****************//
56         for(int i=1;i<=n;i++)
57         {
58             for(int j=1;j<=m;j++) Execution(i,j);//逐格递推
59             if(i!=n)//行间转移:当前行的0到m-1转移到下一行的1到m
60                 for(int j=0;j<bin[m];j++)//bin[m]及第m个插头不可能为1
61                     f[i+1][0][j<<1]=f[i][m][j];//初始化第0格
62         }
63         printf("Case %d: There are %lld ways to eat the trees.\n",u,f[n][m][0]);//最后状态不能再有插头
64     }
65 }

 注意点：（自己的zz错误）
（1）行间转移没判 i!=n        59行
（2）插头从0到m，第m个插头不能为1，写成bin[m+1]         60行
（3）行间转移j<<1写成j>>1，左移1后i+1行的第0位为0         61行
（4）判断都有或没有插头跳过时没&1            30行

转载于:https://www.cnblogs.com/qwertyuiopasdfghjklzxcvbnm/p/11260734.html