插头dp 总结 从懵逼到懵逼

本文部分转自 长沙市雅礼中学陈丹琦Dalao的PPT:基于连通性状态压缩的动态规划问题

引入

Ural 1519 Formula 1

给你一个n×m的棋盘(有的格子存在障碍)，求经过所有非障碍格子的哈密顿回路个数。(n,m<=12)

搜索？复杂度为O((nm)!)，肯定GG

这个时候就要用到插头dp了。

基本概念

先介绍三个基本概念0.0：

① 插头：

两个联通的格子，从一个走向另一个，这里就有一个插头（大白话）

一个格子某个方向的插头存在表示这个格子在这个方向与相邻格子相连。

插头在当前格子的哪边，我们就称这个插头为哪种插头（比如在右边的插头就叫右插头）

② 轮廓线：

因为dp是逐格进行的，故我们可以画一条线来把已经dp完的格子和未dp的格子分开，就叫它"轮廓线"

轮廓线上方与其相连的有m+1个插头，包括m个下插头和1个右插头。

如下图所示：（原谅色的是轮廓线，蓝色的是插头）

③ 插头之间的连通性

如果两个插头在已经dp完的部分连通，我们就称这两个插头联通

状态

记f_{(i,j,S)}为转移完(i,j)，插头的连通性为S时的方案数。

那么如何表示S呢？

首先，一个位置上要么没有插头，要么有插头，且一定与另一个插头连通。

那么我们就可以这样表示S:

在没有插头的地方放一个0，在有插头的地方放一个非0整数，且相联通的插头编号相等。如下图所示：

那么好，对于m=n=12的无障碍棋盘的极限数据, 扩展状态总数为1333113 , 问题已经基本解决．

更高端的状态

仔细想一想，不难发现插头具有以下几个性质：

• 插头若出现，一定两两匹配(两两连通)

• 插头不可能交叉匹配（就是如果从左到右有4个插头a,b,c,d，那么绝对不能出现a,c匹配，b,d匹配，这个用反证法可以证明）

你想到了啥？

括号序列啊！！

我们可以用更加高端的“括号表示法”来表示S

就像这样：（"#"表示没有插头）

这样我们就可以用一个括号序列来表示S

而这个括号序列可以用一个三进制数来存.

等等，三进制Σ(⊙▽⊙"？为了方便运算，我们采用四进制.

状态转移

要分情况了。。。（害怕）

Case 1:

当前所在的格子没有上插头和左插头，有下插头和右插头，相当于构成一个新的连通块．

此时只要在新的S中把"##"变为"()"即可

Case 2:

有上插头和左插头，这种情况下相当于合并两个（或一个）连通分量

Case 2.1

上插头、左插头都是"("插头

Case 2.2

上插头是"("插头，左插头是")"插头

Case 2.3

上插头是")"插头，左插头是"("插头

相当于形成了回路（因为这两个括号一定是匹配的）

Case 2.4

上插头、左插头都是"）"插头

Case 3

上插头、左插头有一个

相当于延续原来的连通分量

这样我们就能开心的DP了

代码么。。。。

懒得写了qwq。

想看具体写法的可以看我的另一篇文章：

USACO Training 6.1.1 Postal Vans 题解

应用

棋盘模型，找路径、环路的最值或者方案数

重要通知

如有疑问、不懂或者觉得不太对的地方，一定要在"评论区"提出。

Questions are welcome.