[已解决]铺地毯（原题链接：http://noi.openjudge.cn/ch0405/9279/）

bangbang-ande

题目在下图：

铺砖

并不需要提供代码！！
主要是讲一下思路

题型：递归

最佳答案

月排行榜 / 总排行榜

Pliosauroidea

2020-9-18 22:46:41

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在前一种情况已经被计算过），递归

具体代码：

1. def count_func(x):
   
2.     count = 0
   
3.     if x == 1:
   
4.         return 1
   
5.     elif x == 2:
   
6.         return 3
   
7.     else:
   
8.         count += count_func(x - 1) + count_func(x - 2) * 2
   
9.         return count
   
10. 
    
11. 
    
12. def non_reverse_count(x):
    
13.     list = []
    
14.     for each in range(0, x):
    
15.         if each == 0:
    
16.             list.append(1)
    
17.         elif each == 1:
    
18.             list.append(3)
    
19.         else:
    
20.             list.append(list[each - 1] + 2 * list[each - 2])
    
21.     return list[x-1]
    
22. 
    
23. 
    
24. def main():
    
25.     while True:
    
26.         input_number = int(input('input\n'))
    
27.         if input_number != -1:
    
28.             print(non_reverse_count(input_number))
    
29.         else:
    
30.             break
    
31. 
    
32. 
    
33. if __name__ == '__main__':
    
34.     main()
    

复制代码

因为递归版本超时，所以附了一个非递归版本
   

跳转到最佳答案楼层

Pliosauroidea

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在前一种情况已经被计算过），递归

具体代码：

1. def count_func(x):
   
2.     count = 0
   
3.     if x == 1:
   
4.         return 1
   
5.     elif x == 2:
   
6.         return 3
   
7.     else:
   
8.         count += count_func(x - 1) + count_func(x - 2) * 2
   
9.         return count
   
10. 
    
11. 
    
12. def non_reverse_count(x):
    
13.     list = []
    
14.     for each in range(0, x):
    
15.         if each == 0:
    
16.             list.append(1)
    
17.         elif each == 1:
    
18.             list.append(3)
    
19.         else:
    
20.             list.append(list[each - 1] + 2 * list[each - 2])
    
21.     return list[x-1]
    
22. 
    
23. 
    
24. def main():
    
25.     while True:
    
26.         input_number = int(input('input\n'))
    
27.         if input_number != -1:
    
28.             print(non_reverse_count(input_number))
    
29.         else:
    
30.             break
    
31. 
    
32. 
    
33. if __name__ == '__main__':
    
34.     main()
    

复制代码

因为递归版本超时，所以附了一个非递归版本
   

405794672

啥题目啊！砖的大小不一样，题目又没说多宽算一列，多宽算一行。两块1*2的可以拼成一块2*2的。问题是，2*2算一个格子，还是1*2算一个格子，甚至3*2算一个格子？或者1*3算一个格子？还有更多可能。

wzdr

Pliosauroidea

Pliosauroidea 发表于 2020-9-21 11:20
3000是ms么。。ms的话递归好像跑不出来emm
我目前做出来的思路就是：
对于x，将其输入函数func:

递归那个词我不会拼，随手找个顺眼的写在函数名上了，无伤大雅23333

Pliosauroidea

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

你在标题中给的网站链接里面那个还考虑了更复杂的情况，那个题的意思是说如果你有一个左右不对称的布局，那么必然存在一个镜面对称的布局，这两种情况在那个题中是算为一个的，所以还要添加一个过程，算出你生成的形状中不对称的布局个数，然后在总生成数中将这一块的重复减掉

bangbang-ande

Pliosauroidea 发表于 2020-9-18 22:46
3000是ms么。。ms的话递归好像跑不出来emm
我目前做出来的思路就是：
对于x，将其输入函数func:

你的代码我大概看懂了，用递归写需要用压位高精加法