AcWing 291. 蒙德里安的梦想 java
原题链接
中等
作者:
fly123
,
2020-09-16 12:43:39
,
所有人可见
,
阅读 411
import java.util.*;
class Main{
static int N=12;
static int M=1<<N;
static boolean[] st=new boolean[M];
static long[][] f=new long[N][M];
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(true){
int n=sc.nextInt();
int m=sc.nextInt();
if(n==0&&m==0)break;
ArrayList<ArrayList<Integer>> state=new ArrayList<ArrayList<Integer>>(); //每次都要刷新
for(int i=0;i<(1<<n);i++){
int cnt=0;
boolean is_valid=true;//中间量用来暂存是否有效
for(int j=0;j<n;j++){
if((i>>j&1)!=0){//当遇到1时说明连续的0结束了,然后判断一下0的个数,如果是奇数置为不合法
if((cnt&1)!=0){
is_valid=false;
break;//如果不合法,说明已经有连续0的个数是奇数,不满足条件了
}
cnt=0;
}
else{
cnt++;//计数0的个数
}
}
if((cnt&1)!=0)is_valid=false;
st[i]=is_valid;
}
for(int i=0;i<(1<<n);i++){//预处理可以从前一列的状态转换到当前列的状态state
ArrayList<Integer> list =new ArrayList<Integer>();
for(int j=0;j<(1<<n);j++){
if((i&j)==0&&st[i|j]==true){
list.add(j);
}
}
state.add(list);//
}
for(int i=0;i<N;i++){//初始化状态数组
Arrays.fill(f[i],0);
}
f[0][0]=1;//初始值为1,只可以是状态为0的
for(int i=1;i<=m;i++){//
for(int j=0;j<(1<<n);j++){
for(int x:state.get(j)){
f[i][j]+=f[i-1][x];//状态计算就是将前面的所有状态都累加起来。
}
}
}
System.out.println(f[m][0]);//0-m-1列都已经填充完成,而且没有延申到m列的,说明恰好填满了。
}
}
}