简单易懂、从零开始的插头DP (一)正如前面写的那样，是从蒟蒻的视点整理总结的。 更改了一些顺序，更改了一些细节。 方便蒟蒻的学习理解)至少本339蒻是这样。 结实的吐司可以直接看其他大人物的博客，学得更快。
你必须学习的前知识：状态压缩DP
虽然还不会学习，但是我推荐学习的前置知识。 zrdxrk/p论文成功之前，建议先读博客再读。
《基于连通性状态压缩的动态规划问题》
什么是塞DP是显而易见的，是关于塞的动态规划。 那么什么是插头呢？
如图所示，在网格中，画一个关于网格点的闭合电路。
对于每个方格、内部，有六种情况
对于电路中的任一个网格，可以看到四条边中只有两条与表示路径的蓝线相交。 这也很清楚。 进去一次，出来一次，c (4，2 )=6。
我们现在把格子中的蓝线从格子的中心指向外面。
这个箭头，也就是所谓的插头。
结合例题，这个主题是洛谷模板问题的弱化版，很多博客都放在模板问题之后的第一个问题上。 结合个人经验，我认为比模板问题更适合第一个问题。
主题： HDU1693 or洛谷P5074
主题：推出n*m网格，部分网格不铺纱，其他网格必须铺贴，可形成多个闭合回路。 有几种铺法？ (1=n，m=12 ) ) )。
那么，将电路模型制成插头模型有什么好处和性质呢？
1 )首先，如果格子上方的格子有下插头，可以看到该格子一定有上插头。 其他方向相似。
按照2:1的方法设置插头，最后一定会构成电路。
3 )一个方格的合理取值只与相邻的方格有关。
观察之三，它表明实际上没有效果。 假设对每个网格执行从上至下、从左至右的处理，则可以记录网格的一部分的状态，并且不需要更多网格的具体状态。
如上图所示，关于当前的网格，只知道红色的网格即可，进而上网格的具体取法不再影响以下的未处理的网格。
掌握了状态压缩的你一定能很容易地算出状态总数。 每个方格有6种，维护n个方格。 总共只有6 n 6^n 6n的状态，是的，结束了，2e9的状态。
别急，我们真的需要2e9的状态吗？ 在这些格子中，指向彼此处理过的格子的插头，显然是废弃物信息。 我们实际上只是知道这些插头。
蓝色是其他格子需要的，黄色是现在格子需要的。我们叫红色的这个线为轮廓线只需知道该轮廓线上是否存在m 1个箭头即可。 共计2米22^ m *22 m2个状态。 再乘坐n和m的话，时空的复杂性会变得充裕。
那么，怎么实现？ 我们必须解决两个问题。
1 )如果知道这些插头，这个方格该怎么填？
2 )填写此方格后，请告诉我下一个方格所需的插头状态，如何从更特殊的、上一行结尾改为下一行开头。
这两个问题其实都不是很难。 稍微想想，就可以独立求解了。 我建议你三思而后行。 图制止以下大法。
问题1 :
0 :这个格子走不动的话，左侧和上方的插头不能存在。
1 )当前格栅有左侧插头和上方插头时，只有一种合理的填补方式。
2 )如果只存在左侧插头，有两种合理的填补方式。
3 )如果只存在上面的插头，它和前面的类型相似，也是两种填补方法。
4 )如果不存在呢？ 只有一种填补方法
问题2 :
解开问题1后，显然也得到了问题2的解答。 毕竟，我们填满了这个格子，自然知道插头的分布。 唯一特殊的是从上一行结束到此行结束的处理。 前面一行的结尾不是有右插头。 那么，如果在表示上一行结束状态的最后，去掉表示右插头是否存在的位置，添加表示没有左插头的位，不就表示该行的第一个状态吗？ 为了便于编写，下面的代码在dp[i][0][mask]中表示迁移后前一行的结束状态。
到此为止，我们得到了理解方法。 成熟的评价机应该自动交流吧。 插头DP还是需要多写。 千万要自己写。 请不要忘记。 这只是模板问题的弱化。
这里提供代码(洛谷交流)
# include iostream # include stdio.h # includecstringusingnamespacestd； int n，m，maxk，a[13][13]； 龙龙DP [ 13 ] [ 13 ] [ 114 ]； () ) ) ) ) )。
;maxk=(1<<(m+1))-1;for (int i=1;i<=n;i++){for (int j=1;j<=m;j++){scanf("%d",&a[i][j]);}}memset(dp,0,sizeof(dp));}void solve(){int prei,prej;dp[0][m][0]=1;for (int i=1;i<=n;i++){for (int k=0;k<=maxk;k++){dp[i][0][k<<1]=dp[i-1][m][k];}for (int j=1;j<=m;j++){prei=i;prej=j-1;for (int k=0;k<=maxk;k++){int b1=(k>>(j-1))&1;int b2=(k>>j)&1;if (!a[i][j]){if (!b1&&!b2) dp[i][j][k]+=dp[prei][prej][k];}else if (!b1&&!b2){dp[i][j][k+(1<<j)+(1<<(j-1))]+=dp[prei][prej][k];}else if (b1&&!b2){dp[i][j][k]+=dp[prei][prej][k];dp[i][j][k+(1<<(j-1))]+=dp[prei][prej][k];}else if (!b1&&b2){dp[i][j][k]+=dp[prei][prej][k];dp[i][j][k-(1<<(j-1))]+=dp[prei][prej][k];}else if (b1&&b2){dp[i][j][k-(1<<j)-(1<<(j-1))]+=dp[prei][prej][k];}}}}printf("%lld\n",dp[n][m][0]);}int main(){int t;scanf("%d",&t);while (t--){init();solve();}return 0;}到这里，插头DP算是入门了一半了，下一篇博客，将会介绍模板题和一系列的简单应用。这道题目里的状态是二进制状态压缩，下面的题目则不然，敬请期待。想必，多半，大概，也许，可能，能日更吧。
电脑前这个努力的帅气身影是谁呢？そう 私 です