插头dp

插头dp 俗称轮廓线dp，

各种网格覆盖问题，范围允许状压解决，常用于计算方案数与联通块权值

插头是tm啥？格子与格子之间的状态

网上图很多，不挂了

说一说对各种状态的理解

已知$b1,b2$

当前有障碍的话，显然不能走

只讨论没有障碍，能走的情况

• $b1=0,b2=0$

增加两个插头，要回路，因此要一个右插头一个下插头

• $b1=0,b2=1$

考虑向右拐，和向下直走

• $b1=1,b2=0$

考虑向下拐，和向右直走

• $b1=1,b2=1$

在右边找个匹配的右插头，然后把原来的两个1都干掉，在现在找到的位置把2干掉，把1重新弄上去

• $b1=2,b2=2$

在左边找个…

• $b1=2,b2=1$

考虑连上，该干啥干啥

• $b1=1,b2=2$

如果不是终点不要记录答案

各种含义

dp[][x] = y, 第x次所表示的价值为y
vis[][x] = y, 第x次所表示的状态为y
cnt[x] = y, cntx这一维度表示的状态数目
hash[x] = y, x这个**位置**在HASH里对应的第y次（在当前状态下）