洛谷 P1044 [NOIP2003 普及组] 栈

洛谷 P1044 [NOIP2003 普及组] 栈

看网上大佬的提示，本题使用卡特兰数解决：
设 n 个数对应出栈请况为 f(n) 个，最后一个出栈的数为 a
那么，
比 a 小的数有 a-1 个，比 a 大的数有 n-a 个
在a入栈前 a-1 个数已经全部出栈，有 f(a-1) 种请况，
在a入栈后出栈前 n-a 个数全部出栈，有 f(a-1) 种请况，
符合乘法法则，即最后一个出栈的数为 a 有 f(a-1) * f(a-1) 种请况。
a从1取到n，递加即可。

所以
f(n) = f(0)* f(n-1) + f(1)*f(n-2) +…+f(n-1)*f(0)
注：f(n)=c(2n,n)-c(2n,n-1)

代码：

#include<stdio.h>
#include<stdlib.h>
int f(int n);
int main()
{
    int n,a;scanf("%d", &n);a=f(n);printf("%d", a);return 0;
}
int f(int n)
{
    int a=0;if(n==0||n==1)//容易判断n为0或1时有一种情况{
    return 1;}else{
    for (int i = 0; i < n; i++ ){
    a += (f(i) * f(n - 1 - i));}}return a;
}

卡特兰数：https://baike.baidu.com/item/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0/6125746?fr=aladdin