梦.:如此短暂

　　最小分成的块数当然就是k+1，分割方法一共只有两种吧？如下图：

　　Submit 1: WA on 2。很可惜，分割方法不只有两种。
　　应该画一条弦，则圆被分成两部分，两部分可以各自看成点数比较少的圆，用两部分分割方法数相乘。以一点为这条弦的一端，枚举另一端求和。
　　以f(n)表示圆上有2n个点时分割方法数，则：

　　这个数是Catalan数，，具体为什么，我不知道。望赐教。
　　注意当n=30时Catalan数会很大。
　　Submit 2: WA on 9。Catalan数比我想象的还大……用那个DP作好了。
　　Submit 3: AC。用Catalan数做虽然是O(n)，但Catalan数的中间计算过程值非常大，必须小高精一下，所以还不如直接用那个DP方程来做。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

//AC
#include <iostream>
using namespace std;
 
int main()
{
    long n;
    long long r[31]={1};
    cin>>n;
    for (int i=1;i<=n;++i)
        for (int j=0;j<i;++j)
            r[i]+=r[j]*r[i-j-1];
    cout<<r[n]<<" "<<n+1<<endl;
    return 0;
}