3912凸多边形的三角形剖分

3912   凸多边形的三角形剖分

题目描述

传说魔法世界的创世神使用过的一件上古神器遗失在一个凸多边形的二维魔法空间中,谁若拥有这件上古神器,将会成为世界之主。修罗王很想拥有这件上古神器,他打算通过若干条互不相交的对角线,把这个多边形剖分成了若干个三角形来寻找,现在的任务是输入凸多边形的边数n,求不同剖分的方案数Cn。比如当n=5时,如图所示,有如下5种不同的方案,所以C5=5。

 

输入格式:

一个整数n。

输出格式:

一个整数,即方案数。
输入样例 复制
5
输出样例 复制
5

说明

5
7
通过提交
时空限制1000ms/128mb
题目来源
评测方式在线评测
题目类型递推
难        度