Description
描述
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条弦，因此A1, A2, ..., A2k分别是这些弦中一条弦的端点，这些弦将圆分成若干个部分。你需要计算N——圆被分成的最少的部分数目P，以及这样的方案数N。
InpPut
输入
The first line contains the integer k (1 <= k <= 30).
第一行包含一个整数k (1 <= k <= 30)。
Output
输出
The first line should contain two numbers N and P delimited by space.
第一行包含两个数字N和P，以空格分隔。
Sample Input
样例输入
2
Sample Output
样例输出
2 3
Analysis
分析
我们可以采用分治的方法，固定某个点，从其上引一条弦，将圆分成左右两部分。我们可以将这两部分看成新的圆，那么方案数就是这两个圆的方案数相乘。
即：f[N] = sigma(f[i - 1] * f[N - i])，其中1 <= i <= N。f[i-1]表示左边的圆，为k = i - 1时的情况，f[N - i]为右边的圆，表示k = N - i时的情况。
这样，我们只要递推一下就可以了。
Solution
解决方案
#includeusing namespace std;const int MAX = 32;long long f[MAX];int main(){ int N; f[0] = 1; f[1] = 1; f[2] = 2; for(int i = 3; i < MAX; i++) { for(int j = 1; j <= i; j++) { f[i] += f[j - 1] * f[i - j]; } } while(cin >> N) { cout << f[N] << " " << N + 1 << endl; } return 0;}
这也算是一道数学题，然而想到分治这一点还是有些难度的。