Codevs 3134 Circle

3134 Circle

题目描述 Description

在一个圆上，有2*K个不同的结点，我们以这些点为端点，连K条线段，使得每个结点都恰好用一次。在满足这些线段将圆分成最少部分的前提下，请计算有多少种连线的方法

输入描述 Input Description

仅一行，一个整数K(1<=K<=30)

输出描述 Output Description

两个用空格隔开的数，后者为最少将圆分成几块，前者为在此前提下连线的方案数

样例输入 Sample Input

2

样例输出 Sample Output

2 3

对于圆上任意一点a，能和任意点连接将圆分成两半 ，前提是圆两边的点数 都是偶数，那么将圆分成的两边以相同的方法分，可知是卡特兰数

提供两种求Catalan数的方法

#include<iostream>

#include<cstdio>

using namespace std;

#define ll long long

ll n,f[];

ll fs(ll x){

    if(x==)return ;

    if(x==)return ;

    if(x==)return ;

    if(f[x])return f[x];

    ll sum=;

    for(ll i=;i<=x-;i++){

        sum+=fs(i)*fs(x-i-);

    }

    f[x]=sum;

    return f[x];

}

int main(){

    scanf("%lld",&n);

    printf("%lld %d",fs(n),n+);

}

递归

#include<iostream>

#include<cstdio>

using namespace std;

#define ll long long

ll f[];

int main(){

    int n;

    scanf("%d",&n);

    f[]=;

    for(int i=;i<=n;i++)

        f[i]=f[i-]*(*i-)/(i+);

    printf("%lld %d",f[n],n+);

}

递推