千辛万苦终于ac
注意本题有个坑,卡了很久
对于单个状态来说,每个状态都是合法的!!不需要单独判断合法状态,因为此题的合法状态判断仅在状态转移时
比如:a状态有奇数个连续的0,b状态正好能插到a状态里,把奇数个0消掉,所以刚开始就不需要排除状态a!
此外,check函数要用一个st数组保存0~(1<<n)-1的结果,相当于做一次初始化,不然每个状态都check会超时
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N=15,M=1<<15;
long long f[N][M];
int n,m;
vector<int> head[M];
int st[M];
//状态j|k竖着不能有连续的奇数个0
int check(int state)
{
//int state=j|k;
vector<int> a;
//state是行的状态,一共多少行就一共多少位,此处为n行
while(state)
{
a.push_back(state%2);
state=state/2;
}
while(a.size()<n)
{
a.push_back(0);
}
for(int i=0;i<a.size();i++)
{
int flag=0;
while(a[i]==0 && i<a.size())
{
flag++;
i++;
//cout<<"flag="<<flag<<endl;
//cout<<"i="<<i<<endl;
}
if(flag%2==1) return 0;
}
return 1;
}
int main()
{
while(cin>>n>>m,n||m)
{
memset(st,0,sizeof st);
memset(f,0,sizeof f);
for(int i=0;i<=M;i++)
head[i].clear();
for(int i=0;i<1<<n;i++)
{
if(check(i))
st[i]=1;
}
//其次,计算状态转移
//当前列和上一列 不能有同一行的横方块(a&b==0)
//当前列和上一列按位或,不能有连续奇数个0
for(int i=0;i<1<<n;i++)
{
for(int j=0;j<1<<n;j++)
{
if((i&j)==0 && st[i|j])
{
head[i].push_back(j);
}
}
}
f[0][0]=1;
for(int i=1;i<=m;i++)
{
for(int j=0;j<1<<n;j++)
{
for(int k=0;k<head[j].size();k++)
{
int t=head[j][k];
f[i][j]+=f[i-1][t];
}
}
}
cout<<f[m][0]<<endl;
}
return 0;
}
二刷 有坑需要注意
- 最后状态为f[m][0],而不是f[m+1][0],意义为已摆好m-1列,且在第m列中由m-1列突出来的方格为0
- 这一题的关键为弄清初始状态和结束状态,初始状态f[0][0]意义为:第0列向第1列伸出的状态为0(也就是第一列没有第0列的伸出),结束状态f[m][0]意为第m列向第m+1列伸出的状态为0
- 状态转移时要注意,除了让两个状态相或之后没有奇数个0之外,还要保证没有两个位置相同的1
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N=1<<15;
long long f[15][N];
int n,m;
vector<int> state;
vector<int> head[N];
int st[N];
//一列一列看,1代表有突出,0代表没有突出,check成立的要求为不能有奇数个0,偶数个0正好能放进去竖着的
int check(int x)
{
vector<int> a;
while(x)
{
int t=x&1;
a.push_back(t);
x=x>>1;
}
while(a.size()<n)
{
a.push_back(0);
}
int flag=1;
for(int i=0;i<a.size();i++)
{
int t=0;
while(a[i]==0)
{
t++;
i++;
if(i==a.size()) break;
}
if(t%2==1)
{
//说明有奇数个0
flag=0;
return 0;
}
}
return 1;
}
int main()
{
while(cin>>n>>m,n|m)
{
state.clear();
for(int i=0;i<=N;i++)
{
head[i].clear();
}
memset(st,0,sizeof st);
memset(f,0,sizeof f);
for(int i=0;i<1<<n;i++)
{
state.push_back(i);
if(check(i)) st[i]=1;
}
for(int i=0;i<state.size();i++)
{
for(int j=0;j<state.size();j++)
{
int a=state[i];
int b=state[j];
if((a&b)==0 && st[a|b])
{
head[i].push_back(j);
}
}
}
f[0][0]=1;
for(int i=1;i<=m;i++)
{
for(int k=0;k<state.size();k++)
{
int a=state[k];
for(auto t:head[a])
{
int b=state[t];
f[i][k]+=f[i-1][t];
}
}
}
////f[m][0]表示 前m-1列都处理完,并且第m-1列没有伸出来的所有方案数。
cout<<f[m][0]<<endl;
}
return 0;
}