[已解决]铺地毯（原题链接：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在前一种情况已经被计算过），递归

具体代码：

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[each - 1] + 2 * list[each - 2])
    return list[x-1]


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()

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

跳转到最佳答案楼层

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

具体代码：

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[each - 1] + 2 * list[each - 2])
    return list[x-1]


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()

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

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:

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