算法
经典的状态压缩/DP问题
状态表示:f[i][j]表示第i列,状态为j时的方案数
其中状态j为一个数字,比如0,1,2,3...但是我们要把j变成2进制,每一位代表竖着列的一个格子,设有5行:
当j=3时: 0
0
0
1
1
当j=5时: 0
0
1
0
1
每个二进制位代表当前对应格子(第i列)的状态,1的时候代表横着放,0代表竖着放
注意事项
pow()函数特别耗时,所以不要把它放到循环判定条件中去,这样每次循环都要调用一次
时间就超了
参考文献
强烈推荐https://www.bilibili.com/video/BV1cv411b7EG/?spm_id_from=333.337.search-card.all.click&vd_source=8493a3e08130914836f4b3e1a5219439
最新代码
#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>
typedef long long intt;
const int N=20;
intt f[N][4096],n,m;//注意是f[N][4096]
bool st[4096];
int pow2[15];
//判断在n位的情况下 一个数字x是否有连续奇数个零若有return false
bool islegal(int x,int n){//n表示x是多少位的数字,返回x合不合法
int res=0;
for(int i=0;i<n;i++){
if(x>>i&1){
if(res&1) return false;
}
else res++;
}
if(res&1) return false;
return true;
}
//初始化st[]数组,并非一劳永逸 因为每次给的行数n不同
void pre_st(int n){
for(int i=0;i<pow2[n];i++){
st[i]=islegal(i,n);
}
}
//初始化f[][]
void pre_f(){
memset(f,0,sizeof f);
f[0][0]=1;//在第0列(虚拟的)只有不横放转才合法,只要放转了就会影响到第一列的情况,所以只有0,0=1,其他都是0
}
//初始化pow2[]和cin加速
void init(){
for(int i=0,j=1;i<15;i++,j*=2){
pow2[i]=j;
}
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
int main(void){
init();
while(cin>>n>>m,n||m){
pre_f();//每次要初始化f[][]
pre_st(n);//每次要初始化st[],因为每次的位数n都不同
for(int i=1;i<=m;i++){//第几列
for(int j=0;j<pow2[n];j++){//本列是哪种摆放
for(int k=0;k<pow2[n];k++){//遍历上一列的摆放方案,看看是否符合本列的拜访
if(st[k|j]&&!(k&j)) f[i][j]+=f[i-1][k];
}
}
}
cout<<f[m][0]<<endl;//最后一列M列一块砖都不能横放了,不然就伸到M+1列去了,而M+1列并不存在,所以合法的情况只有M,0
}
}
旧版 代码
#include<iostream>
#include<math.h>
using namespace std;
#include<algorithm>
#include<cstring>
void preprocess(bool st[],long N){//预处理st[],这个数组是用来判断j这个状态的二进制位是不是连续有奇数个0,有的话st[j]=false
long m=pow(2,N);//m=2的N次方,namely the aggregate of the total status
memset(st,true,m*sizeof(bool));//不能传sizeof(st),这样会返回st这个指针的字节数而不是st所指向的这个bool数组的大小
// 先默认st数组所有状态都是true,都是合法的,即没有连续奇数个0的情况
for(long i=0;i<m;i++){
long cns=0;//记录本轮循环中0的总个数
for(long j=0,temp=(i>>j);j<N;++j,temp=(i>>j)){//给i循环右移,每次移完后看其最低位的二进制位是0还是1
if((temp&1)==1){//如果是1就检查一下0的个数
if((cns&1)==1){//如果是奇数,就直接false
st[i]=false;
break;
}
}else{//如果不是1,0的个数+1
cns++;
}
}
if((cns&1)==1) st[i]=false;//最后还要检查一下高位的情况,比如00011,高位的000需要检查
}
}
int main(void){
long N,M;
while(cin>>N>>M,N||M){
long m=pow(2,N);
bool st[m+1];
preprocess(st,N);//st[]预处理
long f[M+1][m+1];
memset(f,0,sizeof(f));
f[0][0]=1;//在第0列(虚拟的)只有不横放转才合法,只要放转了就会影响到第一列的情况,所以只有0,0=1,其他都是0
for(long i=1;i<=M;i++){
for(long j=0;j<m;j++){
for(long k=0;k<m;k++){
if((j&k)==0&&st[j|k]) f[i][j]+=f[i-1][k];//满足两个条件:1.j\k相同位置不能都横放,不然就叠起来了
// 2.j和k两个向量想yu之后不能出现连续奇数0,否则无法竖着放
}
}
}
cout<<f[M][0]<<endl;//最后一列M列一块砖都不能横放了,不然就伸到M+1列去了,而M+1列并不存在,所以合法的情况只有M,0
}
}