首页 > 代码库 > Codevs 3134 Circle
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 longll n,f[30];ll fs(ll x){ if(x==0)return 1; if(x==1)return 1; if(x==2)return 2; if(f[x])return f[x]; ll sum=0; for(ll i=0;i<=x-1;i++){ sum+=fs(i)*fs(x-i-1); } f[x]=sum; return f[x];}int main(){ scanf("%lld",&n); printf("%lld %d",fs(n),n+1);}
#include<iostream>#include<cstdio>using namespace std;#define ll long longll f[40];int main(){ int n; scanf("%d",&n); f[0]=1; for(int i=1;i<=n;i++) f[i]=f[i-1]*(4*i-2)/(i+1); printf("%lld %d",f[n],n+1);}
Codevs 3134 Circle
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。