插头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为无障碍。
每次转移我们需要将决策格的上，左边转移为下，右边。其中决策格的上，左边会影响到我们当前决策格的决策，为了方便我们将其记为b₁，b₂,设轮廓线为a₀a₁a₂a₃a₄

1.当前决策格有障碍
那么只有这个格子没有连通的时候才是合法情况，转移后轮廓线状态不变。

if(mp[i][j]){
    if(!b1&&!b2) ins(zt,num);}

其中ins（）函数是向轮廓线状态zt的方案加上num（就是简化的 $dp[now][zt]+=dp[las][zt‘]$）。
2.当前决策无障碍：
（1）b₁，b₂都为0
那么只有决策格只有一种情况如图

转移后a_i-1=1，a_i=2。

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

这里即使不判断要连通的格子是不是有障碍，也可以正确给出答案，但是会额外在哈希表中创立许多无效方案，加大了时间复杂度与空间复杂度，所以这里选择在转移前多判断一下。
（2）b₁与b₂其中一个为0
b₂=0时有两张情况，第一种交换a_i-1与a_i

第二种轮廓线不变

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);}
}

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

转移后a_i-1，a_i=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;}
	}
}

b₁=b₂=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）b₁=2，b₂=1

这个转移比较容易

if(b1==2&&b2==1) ins(zt-bit[j]-bit[j-1]*2,num);

（5）b₁=1，b₂=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也讲到了。