3134 Circle

 

 时间限制: 1 s

 空间限制: 32000 KB

 题目等级 : 黄金 Gold

 

 

 

题目描述 

Description

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

输入描述 

Input Description

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

输出描述 

Output Description

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

样例输入 

Sample Input

2

样例输出 

Sample Output

2 3

数据范围及提示 

Data Size & Hint

见题目

分类标签 Tags        

代码

#include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;int h[1001],n;int main(){    scanf("%d",&n);    h[0]=1;    h[1]=1;    for(int i=2;i<=n;i++)       for(int j=1;j<=i;j++)         h[i]=h[i-j]*h[j-1]+h[i];    int ans=h[n];    printf("%d %d",ans,n+1);    return 0;}
             
            
           
          
         

题 解

//考虑到节约空间就用的dfs求卡特兰数//至于卡特兰数递推式的证明个人比较喜欢这个http://blog.sina.com.cn/s/blog_6917f47301010cno.html//但其实把公式背下来就可以了的不用追究#include
         
          #include
          
           #include
           
            #include
            
             using namespace std;long long  k;long long dfs(long long x){    if(x==1)return 1;    return dfs(x-1)*(4*x-2)/(x+1);}int main(){    scanf("%lld",&k);    printf("%lld ",dfs(k));    printf("%lld",k+1);    return 0;}