铺地毯（原题链接：http://noi.openjudge.cn/ch0405/9279/）
本帖最后由 bangbang-ande 于 2021-2-7 22:10 编辑题目在下图：
并不需要提供代码！！
主要是讲一下思路
题型：递归 3000是ms么。。ms的话递归好像跑不出来emm
我目前做出来的思路就是：
对于x，将其输入函数func:
if x==1：
return 1#如果只剩下一层，只有一种情况
elif x==2:
return 3 #如果剩下最后两层，返回3（即两种1*2+一种2*2）
else:
return func(x-1)+2*func(x-2)#即：假定最后一层为1*2，递归，再假定最后一层为竖排的1*2 *2或2*2（此处横排的1*2 *2在前一种情况已经被计算过），递归
具体代码：
def count_func(x):
count = 0
if x == 1:
return 1
elif x == 2:
return 3
else:
count += count_func(x - 1) + count_func(x - 2) * 2
return count
def non_reverse_count(x):
list = []
for each in range(0, x):
if each == 0:
list.append(1)
elif each == 1:
list.append(3)
else:
list.append(list + 2 * list)
return list
def main():
while True:
input_number = int(input('input\n'))
if input_number != -1:
print(non_reverse_count(input_number))
else:
break
if __name__ == '__main__':
main()
因为递归版本超时，所以附了一个非递归版本
啥题目啊！砖的大小不一样，题目又没说多宽算一列，多宽算一行。两块1*2的可以拼成一块2*2的。问题是，2*2算一个格子，还是1*2算一个格子，甚至3*2算一个格子？或者1*3算一个格子？还有更多可能。 {:10_256:}{:10_256:} Pliosauroidea 发表于 2020-9-21 11:20
3000是ms么。。ms的话递归好像跑不出来emm
我目前做出来的思路就是：
对于x，将其输入函数func:
递归那个词我不会拼，随手找个顺眼的写在函数名上了，无伤大雅23333 Pliosauroidea 发表于 2020-9-21 11:20
3000是ms么。。ms的话递归好像跑不出来emm
我目前做出来的思路就是：
对于x，将其输入函数func:
因为题目中只有1*2和2*2的tile，所以只存在单层1*2，双层竖排1*2和2*2三种情况，只要对这三种情况分别讨论后去掉对应tile，就变成了一个递归处理 你在标题中给的网站链接里面那个还考虑了更复杂的情况，那个题的意思是说如果你有一个左右不对称的布局，那么必然存在一个镜面对称的布局，这两种情况在那个题中是算为一个的，所以还要添加一个过程，算出你生成的形状中不对称的布局个数，然后在总生成数中将这一块的重复减掉 Pliosauroidea 发表于 2020-9-18 22:46
3000是ms么。。ms的话递归好像跑不出来emm
我目前做出来的思路就是：
对于x，将其输入函数func:
你的代码我大概看懂了，用递归写需要用压位高精加法
页:
[1]