算法
状态压缩DP
f[i][j] 表示第列状态为j的方案数 , 转移由i - 1 列转移。好好听y总讲都可以听懂。
我本来想懒一下把初始化提前到while外面,结果wa了后来想了一下原来我初始化的时候按得是行数最大枚举的,应该按照有多少行枚举多少。
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 12, M = 1 << 12;
LL f[N][M];
int n, m;
bool st[M];
void init()
{
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)
{
if (cnt & 1) st[i] = false;
cnt = 0;
}
else cnt ++ ;
if (cnt & 1) st[i] = false;
}
}
int main()
{
while(cin >> n >> m, n || m)
{
init();
memset(f, 0, sizeof f);
f[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) && st[k | j])
f[i][j] += f[i - 1][k];
cout << f[m][0] << endl;
}
return 0;
}