2019-11-01

poj-2411-Mondriaan-s-Dream-插头DP做法

缘起

【1】中我们基于状压DP切了，这里在入门了插头DP之后想使用插头DP的思想切一下.

分析

Description
有一个n行m列的棋盘，你可以在里放1*2的骨牌，骨牌之间互相不重叠，问放满整个棋盘有多少种方案数。

Input
输入文件有多组数据，每组数据只有一行为两个整数n和m(1<=W,H<=11)。

Output
每组数据一行为方案总数，若不能够放满整个棋盘输出0。

Sample Input
1 2 
1 3 
1 4
2 2
2 3
2 4
2 11
4 11

Sample Output
1
0
1
2
3
5
144
51205

限制
3s

这里先说说解法思想. 理解了【2】的想法之后, 本题就很好做了. 而且做法绝逼比【1】的做法要自然的多.

和【2】一样，依旧是对轮廓线进行DP. 画图如下

A是格子(i,j-1)（即第i行, 第j-1列的格子）, B是格子(i,j), 其中A是上一次决策完毕的格子, B是当前决策完毕的格子. 决策完A格子之后产生的轮廓线是L1, 决策完B格子之后, 产生的轮廓线是L2. 轮廓线的概念不清楚的童鞋可以参考【2】

wait wait wait~

拜托你别自说自话好伐?

Q: 对于本题而言, 什么叫做决策一个格子呢?

A: 就是决定格子是否填骨牌, 而且如果填的话, 到底是横着放呢? 还是竖着放呢?

Q: 对于本题而言, 什么是插头呢?

A: 和【2】一样, 插头是长在每个格子上的结构. 换言之, 一个格子有4个插头——上下左右. 对于本题, 我们定义, 如果一个格子被骨牌覆盖的话, 则它就具有上插头. 注意, 对于本题的情形, 四个插头中只有上插头有意义, 其余方向的插头我们统统不考虑（即本题每个格子只有一个插头,所以构成轮廓线的m+1个单位长度的竖着的那个单位长度对应的比特位一定是0）. 所以轮构成廓线的m+1个单位长度上的插头只需要考虑存在与不存在. 所以我们可以用一个[0, 2^{m+1})范围内的整数来压缩轮廓线的状态. 而且我们不难知道, 根据轮廓线的状态我们完全可以推定下一次的决策. 进而得到下一条轮廓线的状态值. 举个例子吧~

上图给出了决策完毕A格子之后的棋盘局面, 其中跨越两个格子的竖线代表一块骨牌. 则决策A格子的时候显然是发现（其实就是可以通过图2中决策完B格子之后黄色的轮廓线推断出来）A格子已经被覆盖了的. 则A格子显然就不能再放置任何一块骨牌了. 则决策完A格子之后的蓝色轮廓线就是 000010000, 唯一的1是因为C格子已经被覆盖了, 所以C的上插头是存在的. 而C被覆盖是当时决策格子D的时候做的决定.

1
2
3

令 dp[i][j][k] 是决策完毕第i行第j列的格子之后轮廓线的状态是k时的方案数. 则和【2】一样
初始值 dp[1][0][0] = 1
答案是 dp[n][m][0], 因为决策完最后那个格子之后, 轮廓线变成了图2中的L,而L对应的状态显然是0

定义了DP的问题, 我们再来考虑如何转移状态. 和【2】一样, 我们同样将考虑的问题分成逐格递推和逐行递推.

逐格递推

假设正方形ABCD是格子(i,j-1), 它是上一次决策完毕的格子; 正方形BEFC 是格子(i,j), (1<=i<=n, 1<=j<=m)，它是当前决策完毕的格子。则我们要考虑决策完ABCD之后的轮廓线L1=H->G->A->B->C->F->I->J->K->L 和决策完 BEFC之后产生的轮廓线 L2=H->G->A->B->E->F->I->J->K->L 之间的关系. 其实就是把第j-1个比特位——BC边、第j个比特位——CF边换成了BE边、EF边.

首先我们要根据L1判断一下BEFC 是否存在上插头. 即CF边，亦即第j个比特位是否存在插头.

情形1: 如果存在的话, 则表明BEFC已经被覆盖了,即L1的第j个比特位为1), 则L2的第j个比特位是0（竖边恒为0）. 而至于BC边和BE边的话, 都是0（BC为0是因为它是竖的, BE为0是因为BEFC是按照从左至右、从上至下顺序决策的当前决策到的格子, 不可能BEFC下方的格子已经被覆盖了）. 所以 dp(i,j,L2) = dp(i,j-1,L1), 其中 L2=L1^(1<<j)
情形2: 如果不存在的话, 则表明BEFC尚未被覆盖,即L1的第j个比特位为0)，则就要考虑一下BEFC处格子的骨牌的方法了.
- 情形2.1 如果在BEFC处能横着放骨牌（即BEFC不是一行最后那一列个格子,而且L1的第j+1个比特位是0——即BEFC右侧的格子尚未被覆盖）, 则L1的第j-1(竖边)、j、j+1个比特位都是0, 但是L2的第j-1、j、j+1个比特位分别是0、0、1，其他的比特位都是一样的. 所以L2=L1 | (1<<j+1) 而且 dp(i,j,L2)=dp(i,j-1,L1)
- 情形2.2 如果在BEFC处能竖着放骨牌（即BEFC不是最后一行的格子）, 则L1的第j-1、j个比特位分别是0,0,而L2的第j-1、j个比特位分别是1,0，即L2=L1|(1<<j-1), 而且 dp(i,j,L2)=dp(i,j-1,L1)

逐行递推

换行的情况就是上图中A格子决策完毕之后产生轮廓线L1变到决策完格子B（虚拟格子）之后产生的轮廓线L2. 则L2和L1的关系非常显然, 就是 L2=L1<<1. dp(i+1,0,L2) = dp(i,m,L1).

至此, 我们分析了所有DP转移的情况, 于是可以愉快的打代码了

//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
//#define LOCAL
typedef long long ll;

int n,m, full;
ll dp[15][15][(1<<13)+5];

void sz(int i)
{
	for (int k = 0;k<full>>1;k++)
	{
		dp[i+1][0][k<<1] = dp[i][m][k];
	}
}

inline bool zz(int k, int j) // 判断k的第j个比特位是不是1
{
	return (k>>j)&1;
}

void kk(int i,int j)
{
	for (int k = 0;k<full;k++) // 同【2】, 这里的k是L1的状态,而不应理解为L2的状态值
	{
		if (zz(k,j)) // 情形1
		{
			dp[i][j][k^(1<<j)] += dp[i][j-1][k];
		}
		else // 情形2
		{
			if (j<m && !zz(k,j+1)) // 情形2.1
			{
				dp[i][j][k|(1<<j+1)] += dp[i][j-1][k];
			}
			if (i<n) // 情形2.2
			{
				dp[i][j][k|(1<<j-1)] += dp[i][j-1][k];
			}
		}
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//	freopen("d:\\my.out", "w", stdout);
#endif
	while(scanf("%d%d", &n,&m),n||m)
	{
		memset(dp,0,sizeof(dp));
		full = 1<<m+1;
		dp[1][0][0] = 1;
		for (int i = 1;i<=n;i++)
		{
			for (int j = 1;j<=m;j++) // 逐格DP
			{
				kk(i,j);
			}
			if (i!=n) // 逐行DP
			{
				sz(i);
			}
		}
		printf("%lld\n", dp[n][m][0]);
	}
	return 0;
}

ac情况（唉, 可能是目前我插头的板子还不够好吧, 跑的没【1】的快）

Status	Accepted
Time	969ms
Memory	14540kB
Length	1029
Lang	C++
Submitted	2019-11-02 14:10:46
Shared
RemoteRunId	21014163

参考

【1】https://yfsyfs.github.io/2019/09/19/poj-2411-Mondriaan-s-Dream-%E7%8A%B6%E5%8E%8BDP/

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