BZOJ2822:[AHOI2012]树屋阶梯 卡特兰数

思路:

注意到一个关键条件:一个高度为\(n\)的阶梯,必须要正好用\(n\)个矩形拼出来!

考虑阶梯的角落如何放置一个矩形,不难发现的是,这个矩形必须将剩下的两个区域完全分隔开!否则剩下的部分是不可能用\(n-1\)个矩形拼出来的.

于是我们发现答案序列就是卡特兰数.

Python水.

n=int(raw_input())
a=[]
a.append(1)
a.append(1)
for i in range(2,n+1):
    d=0
    for j in range(0,i):
        d+=a[j]*a[i-1-j]
    a.append(d)
print(a[n])