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])
评论 (0)