插头dp

Posted on Edited on In

插头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次（在当前状态下）