AcWing 291. 蒙德里安的梦想 - Python3 详解
原题链接
中等
作者:
vitalime
,
2022-02-18 07:14:54
,
所有人可见
,
阅读 152
def valid(N,M):
st = [True for i in range(1<<N)]
# 预先处理某一列的所有状态,作为字典
for state in range(1<<N):
cnt = 0
for j in range(N):
res = state >> j & 1 # 从上往下看,判断state的第j位是否是1,是1就代表state第j行是砖
if res:
if cnt % 2 == 1:
# cnt 表示同一列两块砖之间的空隙数目,或者说两个1之间的0的数目
#
# ——————————————————————
# state = "0b10001" = 2**0 + 2**4 = 17
# 1
# 0
# 0
# 0
# 1
# 不合法
# ——————————————————————
# ——————————————————————
# state = "0b100001001" = 2**0 + 2**3 + 2**8
# 1
# 0
# 0
# 0
# 0
# 1
# 0
# 0
# 1
# 合法
# ______________________
st[state] = False
cnt = 0
else:
cnt += 1
if cnt % 2 == 1:
st[state] = False
dp = [[0]*(1<<N+1) for _ in range(M+1)]
dp[0][0] = 1
# 遍历1到M column
for column in range(1,M+1):
for cur_state in range(1<<N):
for prev_state in range(1<<N):
if prev_state & cur_state == 0 and (st[prev_state | cur_state]):
# 问题一:为什么需要当前列状态cur_state & 前一列状态prev_state是0?
# Answer:
# - cur_state记录的是在第column-1列所有可选的空隙中,放一块砖
# 或不放所延伸到第i列的状态是cur_state
# - prev_state记录的是在第column-2列所有可选的空隙中,放一块砖
# 或不放所延伸到第i-1列的状态是prev_state
#
# 状态1(0代表空隙,1代表砖):
# prev_state cur_state
# '0b1000' '0b1000'
# _____________________ _____________________
# column-2 | column-1 column-1 | column
# 1 1 1 1
# 0 0 0 0
# 0 0 0 0
# 0 0 0 0
# 如果放一起, 在column-1的地方重叠了, 这种状态是不合法的
# __________________________________________
# column-2|column-1|column
# 1 1 1
# 0 0 0
# ...
# 问题二:为什么需要st[cur_state | prev_state]是True? 可以是st[cur_state] & st[prev_state] 吗
# 因为dp[i][j]是在i-1列摆好的情况下,再只合法横向放置方块到i-1列中,形成状态j的方案数,所以j的每一位1都是通过在i-1列中0的位置
# 上放砖块延伸来的,这也就意味着,
# 1. 每一位上前一列和当前列不可能同时是1
# 2. 原本合法的i-1列,有可变得不合法,所以需要将当前列的状态或上前一列状态,再检验是否合法。
dp[column][cur_state] += dp[column - 1][prev_state]
# print(dp)
return dp[M][0]
while True:
N,M = map(int,input().split())
if N == 0 and M == 0:
break
res = valid(N,M)
print(res)