AcWing 291. 蒙德里安的梦想-代码注释-算法描述-golang
原题链接
中等
作者:
望哥
,
2020-07-25 20:55:50
,
所有人可见
,
阅读 774
package main
import (
"bufio"
"fmt"
"os"
)
const (
N = 12 // 以便计算最后一列 d[m][0]
M = 1<<N
)
var reader = bufio.NewReader(os.Stdin)
var writer = bufio.NewWriter(os.Stdout)
var st [M]bool // 字典表,存储所有位置的合法情况
func initStatus(n int){
for i:=0;i<1<<n;i++{
cnt:=0
st[i] = true
for j:=0;j<n;j++{
// 遇到1,被占, 且统计的空格数为奇数,无法填充竖着的长方形
if i>>j & 1 > 0 {
if cnt&1>0{
st[i] = false
break
}
cnt=0
continue
}
cnt++
}
// 判断剩下的统计数是否奇数
if st[i] && cnt&1>0{
st[i] = false
}
}
}
// - **数位统计DP**: 所谓的状态压缩DP,就是用二进制数保存状态。为什么不直接用数组记录呢?因为用一个二进制数记录方便作位运算。前面做过的八皇后,八数码,也用到了状态压缩
// - 计数问题: 蒙德里安的梦想, 求把N*M的棋盘分割成若干个1*2的的长方形,有多少种方案。
// - 核心: 找到所有横放 1 X 2 小方格的方案数,因为所有横放确定了,那么竖放方案是唯一的。
// - 状态定义:
// - 集合: 用`f[i][j]` 记录第i列第j个状态的所有合法方案。j二进制中1表示对应行的上一列有横放格子并捅出到本列中。
// - 属性: 方案数
// - 状态计算: `f[i][j] += f[i - 1][k]`
// - i 列和 i - 1 列同一行不同时捅出来 ; 本列捅出来的状态j和上列捅出来的状态k求或,得到上列是否存在连续奇数空行状态,奇数空行不转移。
// - `f[m][0]` 表示没有m列没有涌出。
var f [N][M]int
func solution(n,m int) int{
initStatus(n)
f[0][0] = 1
for i:=1;i<=m;i++{
for j:=0;j<1<<n;j++{
f[i][j] = 0 // 重置统计
for k:=0;k<1<<n;k++{
if j&k==0 && st[j|k] {
f[i][j] +=f[i-1][k]
}
}
}
}
return f[m][0] // 最后一列
}
func main() {
var n,m int
for {
fmt.Fscan(reader, &n, &m)
if n | m == 0 {
break
}
fmt.Fprintln(writer, solution(n,m))
}
writer.Flush()
}