Day11 轮廓线 dp 插头 dp

I. 引入

[USACO06NOV] Corn Fields G

轮廓线 dp 入门题。

逐格枚举，考虑到未决策点仅会受到决策点与未决策点交界处点影响，引入轮廓线（这题是格子）。注意到 $n$ 范围很小，状压。

记 $f(i,j,k)$ 表示枚举到 $(i,j)$ 轮廓线状态为 $k$ 的方案数。

当前格$(i,j)$ 转移到下一格，考虑 $(i,j)$ 填不填：

• 上面已填，$(i,j)$ 必不填，下一格轮廓线第 $j$ 列改为 $0$。

• 左边已填或者 $a(i,j)=0$，$(i,j)$ 必不填，下一格轮廓线不变。

• 其余情况填或不填均可，分别转移。

	f[1][1][0] = 1;
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++)
		{
			int nxti, nxtj;
			(j == m) ? (nxti = i + 1, nxtj = 1) : (nxti = i, nxtj = j + 1);
			for(int k=0; k<=ALL; k++)
			{
				bool up = (1 << j-1) & k;
				bool left = (j == 1) ? 0 : (1 << j-2) & k;
				
				if(i == 1 and up) continue;
				
				if(up) 
					add(f[nxti][nxtj][k-(1<<j-1)], f[i][j][k]);
					
				else if(left or !a[i][j]) 
					add(f[nxti][nxtj][k], f[i][j][k]);
					
				else 
					add(f[nxti][nxtj][k], f[i][j][k]), 
					add(f[nxti][nxtj][k+(1<<j-1)], f[i][j][k]);
			}
		}
	}
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
26

代码

注意到每次转移只与上一格有关，考虑滚动数组。代码

HDU Eat the Trees

插头 dp 入门题。

引入了插头的概念，插头有上下左右四种，通过插头可以保证连通性。

当前格 $(i,j)$ 转移到下一格：

• $(i,j)$ 不能铺，无插头
• $(i,j)$ 要铺，那么一定有两个插头
  • 无左插且无上插 $\to$ 有右插且有下插
  • 仅有左插 $\to$ 有右插或有下插
  • 仅有上插 $\to$ 有右插或有下插
  • 有左插且有上插 $\to$ 无右插且无下插

对于换行转移， $(i,m+1)$ 的转移到 $(i+1,1)$ 中，排除 $(i,m+1)$ 轮廓线最右端有插头的情况，同时 $(i+1,1)$ 轮廓线最左端无左插，补空即可。

在形成若干闭合回路的情况下，终点的轮廓线上无插头。

注意如果从左到右设计状压状态，二进制最低位在轮廓线中体现为最左端。

	f[1][1][0] = 1;
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++)
		{
			for(int k=0; k<=ALL; k++)
			{
				bool up = k & (1 << j);
				bool left = k & (1 << j-1);
				
				if(!a[i][j] and !up and !left) 
					f[i][j+1][k] += f[i][j][k];
				
				if(a[i][j])
				{
					if(!up and !left) 
					{
						if(a[i][j+1] and a[i+1][j]) f[i][j+1][k+(1<<j-1)+(1<<j)] += f[i][j][k];
					}
					if(!up and left)
					{
						if(a[i][j+1]) f[i][j+1][k-(1<<j-1)+(1<<j)] += f[i][j][k];
						if(a[i+1][j]) f[i][j+1][k] += f[i][j][k];
					}
					if(up and !left)
					{
						if(a[i][j+1]) f[i][j+1][k] += f[i][j][k];
						if(a[i+1][j]) f[i][j+1][k+(1<<j-1)-(1<<j)] += f[i][j][k];
					}
					if(up and left)
						f[i][j+1][k-(1<<j-1)-(1<<j)] += f[i][j][k];
				}
			}
		}
		
		for(int k=0; k<=ALL; k++) 
			f[i+1][1][k<<1] = f[i][m+1][k];
	}
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
26
27
28
29
30
31
32
33
34
35
36
37
38

代码

加滚动数组：代码

II. 闭合回路类问题

【模板】插头 dp

在「插头 dp 入门题」的基础上，为了避免多回路，还需记录连通性。

最小表示法

将格子的连通性记录在插头上从而减少状态。

数字相同的插头相连通，$0$ 表示无插头。对于意义相同的状态，不妨取字典序最小的为最小表示法。

括号表示法

考虑到不连通的两个插头不会交叉出现，且相连通的插头不会出现奇数次，类似括号序列的匹配。

$0$ 表示无插头，$1$ 表示左括号插头，$2$ 表示右括号插头。

转移

以括号表示法为例。

$(i,j)$ 转移到下一格：

• 无左插且无上插，相当于新增联通分量。图片

  $\to$ 有下插且有右插，新增下插和右插的左右括号。

• 有左插且有上插，合并联通分量。图片

  $\to$无下插且无右插

  -左插 )上插 (：将下插和右插修改为空。

  -左插 (上插 )：形成闭合回路，当前为终点时合法，否则不合法。

  -左插 (上插 (：将下插和右插修改为空，向后的对应右括号改为左括号。

  -左插 )上插 )：将下插和右插修改为空，向前的对应左括号改为右括号。

• 左插上插恰有一个，延续联通分量。图片

  $\to$ 有下插或有右插，延伸对应括号。

  此时对应的括号情况只在上下左右插头中修改。

和上题一样考虑换行，同样补一个空插头。

实现

• 采用 4 进制存储状态，比 3 进制运算效率高。
• 此时复杂度 $O(nm{4}^n)$ 级别，无用状态较多，考虑哈希表。

对于状态数的计算：考虑无障碍时状态数最多。假设选了 $x$ 个插头（$x$ 一定为偶数）。则状态数为 $\left(\genfrac{}{}{0ex}{}{m+1}{x}\right)\times H(\frac{x}{2})$，其中 $H$ 指卡特兰数。总状态数 ${\sum }_{x=2}^{m+1}\left(\genfrac{}{}{0ex}{}{m+1}{x}\right)\times H(\frac{x}{2})$。在 $n,m=12$ 时，状态数在 $40000$ 左右，实际测试状态数至多只有 $14000$ 不到。

哈希表有两种实现方式：

• 每个键值相同的位置开一个链表。期望复杂度 $O(\frac{n}{mod})$，$mod$ 大小决定了查询复杂度。哈希表代码。
• 若在某键值发生冲突，就不断向后找。

记合法点最大状态数值为 $S$。则总状态数 $O(nmS)$，转移复杂度 $O(\frac{S}{mod})$。

代码（感谢 @libohan0905 当时提供的 Hack 以及卡空间）

加上滚动数组后空间会很小：代码。

参考

基于连通性状态压缩的动态规划——陈丹琦

[HNOI2004] 邮递员

注意到最短路径，在 $n,m>1$ 时走就是一条经过所有点的闭合回路。

注意开 __int128，并将答案乘以 2。

代码

[HNOI2007] 神奇游乐园

记 $f(i,j,k)$ 为决策点为 $(i,j)$，轮廓线状态为 $k$ 的最大收益。

对于 $(i,j)$ 的贡献，可以在 $(i,j)$ 转移到下一格时决定算不算。

与模板题的区别：

• $\sum \to \max$。
• 遇到闭合时不一定终点才合法。闭合时，要求轮廓线仅有左插上插。
• 不一定经过所有点，需要考虑某一个点无插头的情况。

代码

III. 非回路类问题

POJ Tony’s Tour

求左下到右下的简单路径方案数。

考虑添加一条左下到右下的新路径形成回路，构建的新路径应当只有一种通过方案。

下图为一种可行的构造方式。

代码

麦当劳叔叔的难题

同上题，$\sum \to \max /\min$。

下图为一种可行的构造方式。

代码

IV. 铺砖类问题

UVA Tiling Dominoes

令 $m$ 为行列较小数，易得 $m\le 10$。本题测试组数未知，用了多测记忆化的 trick。

SOL1：按行转移，记 $f(i,S)$ 表示填完了前 $i$ 行，第 $i+1$ 行状态为 $S$ 的方案数。每次转移 $2^m$ 生成下一行的状态，时间复杂度 $O(n{4}^m)$。代码

SOL2：按格转移，记 $f(i,j,k)$ 表示当前决策格为 $(i,j)$，且当前决策格 未被考虑，轮廓线状态为 $k$ 的方案数。转移的时候注意特判第一行的情况。代码。

[Code+#3] 白金元首与莫斯科

考虑枚举障碍物做轮廓线 dp，时间复杂度 $O(n^2{m}^2{2}^m)$。代码

考虑正反处理出到 $(i,j)$ 的合法方案数 $f,g$。$(i,j)$ 变成障碍物时在不同状态下将 $(i,j)$ 的 $f,g$ 合并。若采用轮廓线 dp，合并时需要 $O(m)$ 考虑在同一列上均为 $0$ 时填或不填。时间复杂度 $O(n{m}^2{4}^m)$，甚至劣于第一种算法。

考虑记录插头，这样在合并 $f,g$ 时，$f$ 的状态可以确定唯一的 $g$ 状态，合并复杂度降为 $O(1)$。时间复杂度 $O(nm{2}^{m+1})$。无取模代码。AC 代码。