JAVA实现 朴素+优化写法(附详细注释)
状态压缩:
用二进制数保存状态(根据题意来确定0/1分别代表的状态,便于位运算),用十进制数来表示二进制。
课堂笔记
实现过程见代码及注释。
个人觉得比较难懂的是st[]
的预处理,希望注释能帮到大家~
1. 朴素解法
JAVA 代码1
/* 返回一个n*m的矩形,恰好被1*2横或2*1竖的方块填满的方案数量
参考y总的未优化版代码
时间:O()
空间:O()
*/
private static long fixSquare(int n, int m) {
//数据范围1~11;每列的每个空格(n行)有放/不放2种选择,共2^n种情况
//dp[i][j]表示摆放第i列时,第i-1列向后伸出的横方块的状态为j的方案数
//j为一个二进制数( 0 ~ (2^n)-1 ),用0/1表示是否伸出到第i列
long[][] dp = new long[12][1 << 12];
boolean[] st = new boolean[1 << 12]; //status,st[idx]:=处理每列时每种摆放方式idx(状态)是否合法(合法即连续0的个数为偶数)
//预处理st[]。枚举每列合法的摆放方式(状态),并记录在st数组内
//把连续空格数为奇数的状态设定为false,因为空格要摆放竖着的方块,单个空格无法摆放2*1的方块
for (int i = 0; i < (1 << n); ++i) { //共n行,需枚举2^n种,i=[0, (2^n)-1]
st[i] = true; //默认是合法的
int cnt = 0; //记录每段连续0的个数
//从i的二进制数的最低位到最高位,逐段统计连续0的个数,并作相应处理
for (int j = 0; j < n; ++j) {
if ((i >> j & 1) == 1) { //i的当前位==1,一段连续0计数终止,判断奇偶
//如果之前连续0的个数是奇数,竖的方块插不进来,状态不合法
if ((cnt & 1) == 1) {
st[i] = false;
break;
}
cnt = 0; //计数清零,再计算下一段连续0的个数
} else cnt++; //i的当前位==0,计数器+1
}
if ((cnt & 1) == 1) st[i] = false; //末尾再最后判断一次连续0的个数是否为奇数
}
dp[0][0] = 1;
for (int i = 1; i <= m; i++) //遍历每一列i
for (int j = 0; j < (1 << n); ++j) //枚举第i列的每种伸出状态j(从i-1伸到i)
for (int k = 0; k < (1 << n); ++k) //枚举第i-1列的每种伸出状态k(从i-2伸到i-1)
// j & k == 0 表示 i 列和 i - 1列的同一行不同时伸出来(没有冲突的方块填充)
// st[j|k]表示在 i 列状态 j, i - 1 列状态 k 的情况下是合法的(连续0的个数为偶)
if ((j & k) == 0 && st[j | k])
dp[i][j] += dp[i - 1][k]; //此时方案数等于之前每种k状态的数目和
//求的是第m-1列排满并且不向外伸出块的情况(第m-1列的所有n个1*1格子都不伸到第m列)
//0 ~ m-1列是题目中可以摆方块的范围
return dp[m][0];
}
2. 优化解法
朴素写法的代码1中,j
和 k
的两层嵌套循环体,在每处理一列 i
时都需要重新枚举一次,可进行优化。
优化方法:提前将这部分计算好并保存起来,用到时查即可。即提前预处理一遍并保存有哪些状态 k
可以转移到 j
(这里的k
和j
结合朴素解法中的定义来理解)。
JAVA 代码2
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
while (!line.equals("0 0")) { //输入终止条件
String[] sc = line.split(" ");
int n = Integer.parseInt(sc[0]);
int m = Integer.parseInt(sc[1]);
System.out.println(fixSquare(n, m));
line = br.readLine();
}
br.close();
}
/* 返回一个n*m的矩形,恰好被1*2横或2*1竖的方块填满的方案数量
参考y总的[优化版]代码
时间:O()
空间:O()
*/
private static long fixSquare(int n, int m) {
//数据范围1~11;每列的每个空格(n行)有放/不放2种选择,共2^n种情况
//dp[i][j]表示摆放第i列时,第i-1列向后伸出的横方块的状态为j的方案数
//j为一个二进制数( 0 ~ (2^n)-1 ),用0/1表示是否伸出到第i列
long[][] dp = new long[12][1 << 12];
//status,st[idx]:=处理每列时每种摆放方式idx(状态)是否合法(合法即连续0的个数为偶数)
boolean[] st = new boolean[1 << 12];
//transfer,保存有哪些状态k可以转移到j(这里k、j是未优化版本中的概念)
ArrayList<ArrayList<Integer>> trans = new ArrayList<>(1 << 12);
//预处理st[]。枚举每列合法的摆放方式(状态),并记录在st数组内
//把连续空格数为奇数的状态设定为false,因为空格要摆放竖着的方块,单个空格无法摆放2*1的方块
for (int i = 0; i < (1 << n); ++i) { //共n行,需枚举2^n种,i=[0, (2^n)-1]
st[i] = true; //默认是合法的
int cnt = 0; //记录每段连续0的个数
//从i的二进制数的最低位到最高位,逐段统计连续0的个数,并作相应处理
for (int j = 0; j < n; ++j) {
if ((i >> j & 1) == 1) { //i的当前位==1,一段连续0计数终止,判断奇偶
//如果之前连续0的个数是奇数,竖的方块插不进来,状态不合法
if ((cnt & 1) == 1) {
st[i] = false;
break;
}
cnt = 0; //计数清零,再计算下一段连续0的个数
} else cnt++; //i的当前位==0,计数器+1
}
if ((cnt & 1) == 1) st[i] = false; //末尾再最后判断一次连续0的个数是否为奇数
}
//预处理,更新保存有哪些状态k可以转移到j
for (int j = 0; j < (1 << n); ++j) {
trans.add(new ArrayList<Integer>());
for (int k = 0; k < (1 << n); ++k)
// j & k == 0 表示 i 列和 i - 1列的同一行不同时伸出来(没有冲突的方块填充)
// st[j|k]表示在 i 列状态 j, i - 1 列状态 k 的情况下是合法的(连续0的个数为偶)
if ((j & k) == 0 && st[j | k])
trans.get(j).add(k);
}
dp[0][0] = 1;
for (int i = 1; i <= m; i++) //遍历每一列i
for (int j = 0; j < (1 << n); ++j) //枚举第i列的每种伸出状态j(从i-1伸到i)
for (int k : trans.get(j)) //查询trans中保存的可转移到状态j的状态k
dp[i][j] += dp[i - 1][k]; //此时方案数等于之前每种合法k状态的数目和
//求的是第m-1列排满并且不向外伸出块的情况(第m-1列的所有n个1*1格子都不伸到第m列)
//0 ~ m-1列是题目中可以摆方块的范围
return dp[m][0];
}
}
参考资料
注释中,部分参考了@Alier ,@松鼠爱葡萄 的题解。
哈哈 我优化完后更慢了0.0
这道题Java有点问题,暴力是最快的