AcWing 291. 蒙德里安的梦想
原题链接
中等
作者:
henhen敲
,
2020-04-25 17:34:54
,
所有人可见
,
阅读 492
import java.io.*;
class Main{
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int nextInt()throws Exception{
in.nextToken();
return (int)in.nval;
}
static long[][] f;
static boolean[] st;
public static void main(String[] args) throws Exception{
int n, m;
n = nextInt(); m = nextInt();
while(n!=0&&m!=0){
st = new boolean[1<<n];
for(int i=0; i<1<<n; i++){//这里应该注意 st 是表达当前状态下是否能放下竖立摆放的块
// 或者全都横放
st[i] = true;
int cnt = 0;
for(int j=0; j<n; j++){
if((i>>j&1)==1){
if((cnt&1)==1){
st[i] = false;
break;
}
}
else cnt++;
}
if((cnt&1)==1)st[i] = false;
}
f = new long[1<<n][m+1];
f[0][0] = 1;
for(int j=1; j<=m; j++)
for(int i=0; i<(1<<n); i++)
for(int k=0; k<(1<<n); k++)
if((i&k)==0&&st[i|k])
f[i][j] += f[k][j-1];
out.println(f[0][m]);
n = nextInt(); m = nextInt();
}
out.close();
}
}