SP3883 题解

和其他两篇题解的 dp 思路稍许不同，因为有两维且是状压。

正常来说一维可能是不够的，因为有可能枚举到一列时后面一行用

1 \times 2

的骨牌铺导致多了个尾巴，那我们就以后面一行尾巴的状态来进行状压。

设状态

dp_{i,j}

表示前

i

行均填满，第

i + 1

行多出来的尾巴二进制状态是

j

时的方案数。比如

dp_{4,5}

的情形如下：

那么还差一个转移方程。

dp_{i,j}

能转移到

dp_{i-1,k}

有一个必然条件，那就是

j

和

k

的与运算必须是

0

。如果不是

0

的话，那么必然存在

j

和

k

的某一位都是

1

，那么中间一个格子会被占用两次，这显然是不合法的。还有一种情况是转移了之后中间一列的格子无法覆盖。在这种情况下，中间一列空出来的值（转化为二进制数）不可能为

0,3,6

。

3

和

6

都可以用一张

2 \times 1

的骨牌覆盖完。当这种情况也合法的话，状态就可以转移了。

CPP

#include <iostream>
using namespace std;
int dp[35][8],n; 
int main()
{
	dp[0][0] = 1;//初始第0行没有尾巴，值为1
	for(int i = 1;i <= 30;i ++)
		for(int j = 0;j < 8;j ++)
			for(int k = 0;k < 8;k ++)
				if(!(j & k) && !((7 - j - k) % 3))dp[i][j] += dp[i - 1][k];//7-j-k:中间没有被占用的格子的二进制状态
	while(cin >> n && n != -1)cout << dp[n][0] << '\n';//输出答案显然不能留尾巴
}

这题的数据范围只有

30

，可以使用打表大法。（当然应该没有人会这么做吧）

CPP

#include <iostream>
using namespace std;
int dp[35] = {1,0,3,0,11,0,41,0,153,0,571,0,2131,0,7953,0,29681,0,110771,0,413403,0,1542841,0,5757961,0,21489003,0,80198051,0,299303201},n; 
int main()
{
	while(cin >> n && n != -1)cout << dp[n] << '\n';
}

文章操作

相关推荐

评论

SP3883 题解