UVA 10303 How Many Trees?

本文主要是介绍UVA 10303 How Many Trees?，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：设f[i]表示一共有i个元素时二叉搜索树的个数，那么依次取1～n-1作为根节点，那么左右子树元素的个数就分别是(0，n-1),......,所以f[n] = f[0]*f[n-1]+f[1]*f[n-2]...+f[n-1]f[0],其实也就是Catalan数，高精度的计算，递推公式是f[n]=(4n-2)/(n+1)*f[n-1]

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 4000;int f[MAXN][MAXN];
int l[MAXN];void div(int x){int *t = f[x],y=x+1,cur=0;for (int i = l[x]-1; i >= 0; i--){cur = cur*10+t[i];t[i] = cur / y;cur %= y;}int j;for (j = l[x]-1; j > 0 && !t[j]; j--);l[x] = j + 1; 
}void mul(int x){int &i = l[x],c=0,y=4*x-2;int *p=f[x-1],*t=f[x];for (i = 0; i < l[x-1] || c; i++){c += p[i] * y;t[i] = c % 10;c /= 10;}
}void print(int x){int *p=f[x];for (int i = l[x]-1; i >= 0; i--)printf("%d",p[i]);printf("\n");
}int main(){int n;memset(f,0,sizeof(f));f[1][0] = 1;l[1] = 1;for (int i = 2; i <= 1000; i++){mul(i);div(i);}while (scanf("%d",&n) != EOF){print(n);}return 0;
}

这篇关于UVA 10303 How Many Trees?的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---