SGU 130 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=130

130. Circle

time limit per test: 0.50 sec.
memory limit per test: 4096 KB

On a circle border there are 2k different points A1, A2, ..., A2k, located contiguously. These points connect k chords so that each of points A1, A2, ..., A2k is the end point of one chord. Chords divide the circle into parts. You have to find N - the number of different ways to connect the points so that the circle is broken into minimal possible amount of parts P.

在圆上有 2k 个不重合的点 A1, A2, ..., A2k, 通过这些点可以作k条弦,使得每个点都恰好属于一条弦。这样我们就把这个圆分成了很多区域,你要求出 N 个方案数,使这些弦将圆划分的区域数量最小。

Input

The first line contains the integer k (1 <= k <= 30).

输入 K.

Output

The first line should contain two numbers N and P delimited by space.

输出方案数量和最少的区域数量,用空格隔开。

Sample Input

2

Sample Output

2 3

只要让所有的弦不相交所得到的区域数量就是最少的,当然最少区域数量就是 k+1.
假设选取A1点,那能与A1相连并且最终没有弦相交的点就是A2,A4,A6......,这样这条边两边就变成两个规模较小的圆,乘一下就可以了。

CODE

#include<iostream>
#include<string.h>
using namespace std;
 
int main()
{
  int i,j,k;
  long long D[31];
  memset(D,0,sizeof(D));
  D[0]=1;D[1]=1;D[2]=2;
  for(i=3;i<=30;++i)
    for(j=1;j<=i;++j)
      D[i]+=D[j-1]*D[i-j];
  cin>>i;
  cout<<d[i]<<" "<<i+1<<endl;
  return 0;
}
» 本博客采用署名 2.5 中国大陆许可协议进行许可,本文版权归作者所有,欢迎转载,但必须在明显位置给出原文连接。
anyShare分享到:
发表评论?

0 条评论。

发表评论

注意 - 你可以用以下 HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>