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 的骨牌覆盖完。当这种情况也合法的话，状态就可以转移了。

#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，可以使用打表大法。（当然应该没有人会这么做吧）

#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';
}