1813: 凸多边形分割问题（Catalan数）

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：4 Solved：3

Description

求一个凸多边形区域划分成三角形区域的方法数？


以凸多边形的一边为基，设这条边的2个顶点为A和B。从剩余顶点中选1个，可以将凸多边形分成三个部分，中间是一个三角形，左右两边分别是两个凸多边形，然后求解左右两个凸多边形。

Input

输入凸多边形的边数

Output

输出方法数量

Sample Input Copy 

5

Sample Output Copy 

5

HINT

设问题的解f(n)，其中n表示顶点数，那么f(n) = f(2)*f(n-1) + f(3)*f(n-2) + ......f(n-2)*f(3) + f(n-1)*f(2)。f(2)*f(n-1)表示三个相邻的顶点构成一个三角形，那么另外两个部分的顶点数分别为2和n-1。 设f(2) = 1，那么f(3) = 1, f(4) = 2, f(5) = 5。结合递推式，不难发现f(n) 等于h(n-2)

Source/Category

SubmitSubmit RecordStatisticsShowOff!