hdu 2067 小兔的棋盘【关于Catalan数的一点学习】

hdu   2067   小兔的棋盘                   题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2067

background knowledge：什么是卡特兰数呢？给出一个实例来引出，一个栈（无穷大）的进栈序列为1，2，3，……，n，有多少个不同的出栈序列？凡是符合这个特征的数都是卡特兰数，其前几项为1，1，2，5，14，42，132…。由于课本上也没给出推导证明，这里就不深究了，只给出公式（两递推一通项）。

formula：

（I）h(n)=h(0)×h(n-1)+h(1)×h(n-2)+…+h(n-1)×h(0)     (n≥2)

（II）h(n)=((4n-2)/(n+1))×h(n-1)

（III）h(n)=C(2n,n)/(n+1)     (n=1，2，3，…)

题目分析：为什么这个题要用卡特兰数呢？因为它的过程可以抽象成前例的样子，比如说先往下走，在往下走了一步的情况下，就可以往右走一步，这样向下走就等同于进栈，向右走就等同于出栈，有了卡特兰数的知识，这题就相当水了。（别忘了最后要乘2啊，因为只要满足不穿过对角线的话，先往下和先往右都可以的）

code:

#include<stdio.h>
__int64 a[36];
int main()
{
    int i,j;
    for(a[0]=1,i=1;i<36;i++)
    {
        for(j=0;j<=i;j++)
        {
            a[i]+=a[j]*a[i-j-1];
        }
    }
    j=1;
    while(~scanf("%d",&i),i!=-1)
    {
        printf("%d %d %I64d\n",j++,i,a[i]*2);
    }
    return 0;
}

hdu 2067 小兔的棋盘【关于Catalan数的一点学习】,布布扣,bubuko.com

hdu 2067 小兔的棋盘【关于Catalan数的一点学习】

原文：http://blog.csdn.net/blogs_of_slicer/article/details/20479279