插头DP 备忘

以前一直觉得没必要学，就是普通的状压，发现不学一下写起来有点难受的。

最好的学习资料大概就是 cdq 的论文了。

原文叫 基于连通性状态压缩的动态规划问题。

最常见的问题形式就是给个网格图，求某种回路或者类似的图形最优化或者计数。

核心思想是把他转化为 \(dp\)，需要满足无后效性和最优子结构。

一般的状压是 \(2^n\)，这个一般是跑不满的 \(bell(n)\)。

把能继续往下延伸的格子叫做插头，维护的是插头的联通性。

一般来说 \(n\) 和 \(m\) 中一定有一个较小，大概 \(7,8\) 左右。

用 \(S\) 来记录一行的联通性，用最小表示法。（空的记录为 \(0\)）

最小表示法有两种。

1.每个连通块都编号，从 \(1\) 开始。

2.和他联通的编号最小值。

我一般用 \(2\)。

转移有逐行递推和逐格递推，一般来说逐格递推复杂度较优。

转移得分类讨论去修改轮廓线，视时限写 \(O(1)/O(m)\)，\(O(m)\) 较为好写。

实现方法：转移到新的状态的时候，如果未出现过则扔进哈希标号，哈希可以直接用 \(p\) 进制，便于 \(O(1)\) 维护轮廓线的修改。

小优化：\(2^k\) 进制常数较小，常见 \(8-Based\)。

还存在括号表示法和广义括号表示法。

括号表示法：插头两两匹配，不会交叉，用 \(4\) 进制，\(012\) 来表示括号匹配，\(1,2\) 为 \((,)\)。（有独立插头不用匹配掉的情况可以记为 \(3\)）

广义括号表示法：连通块不交叉，但是不止一个，最左侧为 \((\)，最右侧为 \()\)，中间为 \()(\)，如 \(\{1,2,2,3,4,3,2,1\}\) 可以是 \((-(-)(-(-()-)-)-)\)。

染色题，\(4,8\) 联通相关没有插头的概念，维护颜色和联通情况就可以。

非棋盘模型，只有 \(|i-j|\le x\)，\(x\) 很小时才有边，也可以联通性状压 \(dp\)，例：生成树计数。

剪枝卡常技巧：缩减状态，最优性，可行性两方面入手，再考虑边界情况。