状态压缩dp
(状态压缩dp) $O(n^3)$
算法的艺术
时间复杂度
n^3
C++ 代码
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
// f[i][j]代表的是第i列被捅出来的数目为j的所有情况
const int N = 12, M = 1 << N;
int n, m;
long long f[N][M];
bool st[M];
int main()
{
// 一直读直到n = 0 m = 0
while (cin >> n >> m, n || m)
{
// 遍历行数所有状态
// 初始化st数组
for (int i = 0; i < 1 << n; i ++ )
{
int cnt = 0;
st[i] = true; // 首先默认是正确的
for (int j = 0; j < n; j ++ )
if (i >> j & 1) // 碰到1了就要判断连续0的数目了
{
if (cnt & 1) st[i] = false; // 奇数为false
cnt = 0; // 数目归0
}
else cnt ++ ; // 连续0数目加1
if (cnt & 1) st[i] = false;
}
memset(f, 0, sizeof f);
f[0][0] = 1; // 第0列被捅出来数目为0的数目只能有1个
for (int i = 1; i <= m; i ++ )
for (int j = 0; j < 1 << n; j ++ )
for (int k = 0; k < 1 << n; k ++ ) // 因为每个格子必须全部沾满,所以才有了下面两个条件
if ((j & k) == 0 && st[j | k]) // 遍历所有情况 找到符合条件的才加进来
f[i][j] += f[i - 1][k];
cout << f[m][0] << endl;
}
return 0;
}