UVA10303 题解

ikunTLE · 2024-08-01 20:43:30 · 题解

题目传送门

题目大意

请求出有多少种不同的二叉搜索树可以使用一个大小为 n 的数字集合构建，且可使得使得集合中的每个元素都与二叉搜索树中的一个节点关联？

思路

二叉搜索树有如下几个重要的特点：

若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。

设 f_i 为前 i 个元素二叉搜索树的个数，初始化 f_0=1，并列出式子：

f_n=\sum_{i=0}^{n-1}f_i\times f_{n-i-1}

科普：这个公式就是卡特兰数的推导公式。

注意事项

需要用高精，而且是小常数。

核心代码

f[0]=1;
for(int i=1;i<=1000;++i)
    for(int j=0;j<i;++j)
        f[i]+=f[j]*f[i-j-1];

Python 自带高精，推荐使用 Python。

AC CODE

f=[0]*1005
f[0]=1
for i in range(1,1001):
    for j in range(i):
        f[i]+=f[j]*f[i-j-1]
try:
    while True:
        n=int(input())
        print(f[n])
except EOFError:
    pass