Ural 1519 Formula 1 插头DP进阶

缘起

【1】中插头DP入了个小门. 而且在【1】中也提到了本题. 即本题在【1】的基础上杂糅了”连通性”. 即状压轮廓线的时候要多状压进一个信息维度——当前已经决策完毕的格子们的连通性. 所以本题可以视作在【1】的进阶. 而且墙裂推荐先学习【1】, 本文的思路就很自然了.

Ural 1519 Formula 1

分析

1
2
问题描述
给你一个 n*m 的棋盘，有的格子是障碍，问共有多少条回路使得经过每个非障碍格子恰好一次． m, n ≤ 12．

1572841058782

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
如图， m = n = 4， (1, 1), (1, 2)是障碍，共有 2 条满足要求的回路．

【输入】
本题就一组数据, 第一行是n和m, 2 ≤ N, M ≤ 12, 然后是n*m的字符矩阵, *表示是障碍物. . 表示是空白.

【输出】
回路的个数. 输入保证这个数量不会超出 long long 的范围.

【样例输入】
4 4
**..
....
....
....
答案是2

4 4
....
....
....
....
答案是6

【限制】
1s

本题其实在【1】中也已经预告过. 本题其实就是在【1】的基础上杂糅进了连通性——即我们需要在考虑线段覆盖的基础上还需要考虑这些插头的连通性——毕竟本题题面和【1】中的题面唯一的区别在于本题需要一条（显然非平凡）哈密顿回路，而【1】可以允许任意多条（非平凡）哈密顿回路. 所以我们不能允许下面的覆盖出现. 即下面的覆盖（即【1】中的图4）不是我们要考虑的.

1572957249924

回忆【1】中的做法, 【1】中我们其实是状压轮廓线上插头的存在性（存在计1, 不存在计0） ,然后决策完最后那个格子的时候, dp[n][m][0] 就是答案. 本题将延续【1】中的方法. 逐步破解本题.

ps: 这里说点废话, 关于此题, 因为是 CDQ 的入门第一题, 所以网上的题解铺天盖地. 但是如果你去看的话, 会发现N多神犇其实写的不是太清楚. 可能是神犇们觉得太显然了吧~ 但是不清不楚给小白带来的痛苦就是觉得 “哇~ 插头DP入门好难哇~”（事实上，的确没那么简单~ 但也不是遥不可及）. 本文将延续【1】（墙裂推荐大家去看看【1】，看懂【1】之后就会觉得这里的思路好自然~）

本文的宗旨（也是本人写作的一贯风格）是: 丝毫不强行解释, 而是站在小白的角度（因为本人就是）抽丝剥茧, 一点一点极为自然的，站在人思考的角度把题目解出来.

延续【1】的风格, 和【1】一样, 我们状压的依旧是轮廓线的状态. 但是我们说, 轮廓线的状态仅仅表示”插头存在性”是不够的! 也就是如果插头存在, 则记轮廓线的一段为1， 插头不存在, 则记轮廓线的一段为0. 这是不行的!

为什么? 看下图

1572958885086

阴影部分是障碍格子. 看到图1和图2中的黄色轮廓线, 如果仅仅使用插头存在与否的话, 那两条轮廓线的值都是 100110111, 但是能够使得轮廓线到达这一状态的图1中的黑色回路显然是不合法的. 因为它由两条哈密顿回路构成. 所以如果仅仅考虑轮廓线上的插头存在与否的问题的话, 显然是会多算的.

错误是显然的——因为没有把插头的连通性考虑进去. 那么怎么把连通性也考虑进去呢? 这里介绍网上流行的”括号表示法”. 所谓括号表示法目的就是得到轮廓线的状态（就像是【1】中使用二进制压缩轮廓线的状态一样）.

括号表示法步骤是什么呢? 首先, 观察图1中在轮廓线上方的哈密顿回路（或者说是哈密顿回路被截出来的部分, 你把轮廓线想成是海平面, 哈密顿回路是冰山, 则轮廓线上方的哈密顿回路就像是浮在海平面上方的冰山），截出的哈密顿回路的部分由A–D、B–C、E–F 三段构成. 其中A、B、E是段的起点, 而D、C、F是段的终点. 如果将起点用1表示,终点用2表示, 如果轮廓线上不存在插头的话, 就用0表示. 则图1中的轮廓线表示为 100120212, 而同理分析图2, 黑色的哈密顿回路被黄色的轮廓线截出的部分由A–F、B–C、D–E三段构成. A、B、D分别是这三段的起点，而F、C、E 分别是这三段的终点. 所以图2中的黄色轮廓线表示为100120122. 即

  • 用【1】中的01表示法, 图1、图2中的黄色轮廓线都将表示为100110111
  • 用括号表示法（即012表示法）, 图1，图2中的黄色轮廓线将分别表示为 100120212 和 100120122

如果将 1看做左括号的话, 2看做右括号, 0忽略掉的话, 则100120212就是 ( ( ) ) ( ), 而 100120122 就是 ( ( ) ( ) )

有点直觉的人都会发现前者给人的感觉就是不连通的（因为最外层没有一个大括号将整体包起来）, 而后者就是连通的（因为最外层存在一个大括号将整体包起来）!

所以我们就知道了——要刻画轮廓线的状态的话， 要用0、1、2三个数字来表示. 即使用三进制. 但是按照网上诸多神犇的说法——3进制没有四进制（2^2）快, 所以采用四进制更好. 于是我们知道了, 用四进制来刻（状）画（压）轮廓线. 轮廓线的状态有 4^{m+1} 至多 4^13=67108864 种状态!

仿照【1】, 我们令

1
2
3
4
令dp[i][j][k] 是当前已经决策完 第i行, 第j列的格子（1<=i<=n, 1<=j<=m）,轮廓线状态是k时的方案数.
0<=k<full = (4<<(m+1)). 网上很多文章都没有清楚的指明插头dp的含义. 让我这种小白猜了好久~苦啊~ QAQ
dp的初始值是 dp[1][0][0] = 1
答案是 dp[n][m][0]

但是遗憾的事情发生了

1572960078652

因为m的范围到达了12, 所以数组是开不下的. 但是为了说明思路, 我们假设 数据的范围较小, 譬如 n,m<=10, 然后我会延续【1】中的思路将程序写出来, 当然，显然是无法ac的. 因为m的范围都不对. 但是我会将写好的程序和网上神犇的代码对拍, 发现没有问题，则至少说明思路没有问题. 然后再改进空间复杂度.

既然dp的含义和初始值、以及我们的目标值都已经知道了. 我们就来思考状态转移的事情.

和【1】一样, 分为逐格递推和逐行递推. 逐行递推, 也就是换行也是简单的. 和【1】中的图5一样分析知道,

1
2
3
4
for i<n
L2=L1<<2. 则有 dp[i+][0][L2] =dp[i][m][L1]
其中 L1是决策完(i,m)格子之后的轮廓线, 而L2是决策完(i+1,0)格子之后的轮廓线.
这里之所以是<<2而不是 <<1, 是因为本题是四进制, 而不是二进制.

再分析一下障碍格子. 和【1】的图6一样分析, 很容易知道——只有障碍格子的上左两条边都没有插头的时候, 

1
L2=L1, dp[i][j][L2]=dp[i-1][j][L1]

否则

1
dp[i][j][L2]=0, for L2 s.t. 障碍格子上左两边至少一个有插头

好了, 分析完这些特殊情形, 我们来考虑正常格子的逐格递推. 如果令p和q分别是j-1段和j段的轮廓线的比特位情况（即p、q分别是是L1的左段、上段轮廓线）分别为p和q的话， 则【1】中其实是根据p=0,q=0、p=0,q=1、p=1,q=0、p=1,q=1 四种情况分情况讨论的. 只不过将p=0,q=1、p=1,q=0 这两种情况合并成了【1】中的情况3而已. 而本题, p,q的取值范围是0、1、2. 所以有 3*3=9 种情况. 也就是我们在不知晓能不能合并的情况下, 理论上是有9种情况需要分类讨论的.

为了说明方便, 令

1
2
3
4
for(int j = 0;j<=m;j++)
{
	jz[j] = j<<1;
}

jz的值显然是0,2,4,6,8,10… 因为本题是四进制, 所以移位的时候移动位数都是2的倍数.

  1. p=0, q=0

    1572996525652

    ​ 图3

    其实就是【1】中的图1. 当前决策完毕格子是BGDC. 则因为每个格子一定 要有2个插头, 一个是进的, 一个是出的. 所以L2的j-1、j个比特位(即BG、GD)一定都不是0. 所以L2相比L1就是第j-1、第j个比特位变化了而已——由L1的both=0变成L2的both不为0, 不为0的话, 则一定是1、2，即形成了一对新的括号. 所以我们知道

    1
    dp[i][j][k+1<<2(j-1)+2*]

参考

【1】[https://yfsyfs.github.io/2019/11/01/HDU-1693-Eat-the-Trees-%E6%8F%92%E5%A4%B4DP%E5%85%A5%E9%97%A8/