题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int N=12,M=1<<N;//每一次测试的
bool st[M];//表示每一种情况是否可以
long long f[N][M];//这里的i是表示当前在第i列 j表示的是上一列延伸出来的横
int n,m;
int main(){
while(cin>>n>>m && (n||m)){
//首先先测试所有的情况判断当前是否是连续为0的奇数点
for(int i=0;i<1<<n;i++){
st[i]=true;
int cnt=0;//用来计算是否有连续个奇数
for(int j=0;j<n;j++){
if(i>>j&1){
if(cnt & 1){
st[i]=false;
cnt=0;
break;
}
}else{
cnt++;
}
}
if(cnt &1){
st[i]=false;
}
}//上面这个将
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) == 0 && (st[j | k]))
// j & k == 0 表示 i 列和 i - 1列同一行不同时捅出来
// st[j | k] == 1 表示 在 i 列状态 j, i - 1 列状态 k 的情况下是合法的.
f[i][j] += f[i - 1][k];
cout << f[m][0] << endl;
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla