AcWing 291. 蒙德里安的梦想
原题链接
中等
作者:
hhu-菜菜
,
2021-05-20 12:11:29
,
所有人可见
,
阅读 211
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = 12, M = 1 << N;
boolean[] st = new boolean[M];
long[][] f = new long[N][M];
//先计算任意一个数的空白存在情况,为j | k来做准备
while (true) {
//当m,n=0是跳出true的循环
int n = sc.nextInt();
int m = sc.nextInt();
if (m == 0 && n == 0) break;
for (int i = 0; i < 1 << n; i++) {
int count = 0;
st[i] = true;
for (int j = 0; j < n; j++) {
if (((i >> j) & 1) == 1) {
if ((count & 1) == 1) {
st[i] = false;
}
count = 0;
} else {
count++;
}
}
if ((count & 1) == 1) st[i] = false;//最后的count也需要计算,这个容易忘
}
//重置
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
f[i][j] = 0;
}
}
f[0][0] = 1;//base case很重要
for (int i = 1; i <= m; i++) {
for (int j = 0; j < 1 << n; j++) {
for (int k = 0; k < 1 << n; k++) {
if (st[(j | k)] == true && (j & k) == 0 ) {
f[i][j] += f[i - 1][k];
}
}
}
}
System.out.println(f[m][0]);
}
}
}