题目描述

众所周知，纪中的信息学竞赛是很强的。专家为看看纪中的学生是否名符其实，给几个初一的学生（当然包括信息学小牛的你）出了几个问题来考考他们。其中一个问题是：在N个数乘积K1K2……KN中插入足够的括号，使得每一个乘积恰好是两个因子的乘积。例如K1K2K3K4能被括号括成：

（（K1K2）（K3K4）） （（（K1K2）K3）K4） （K1（（K2K3）K4）） ……

在加括号的过程中不允许改变Ki的顺序。现在专家要你们告诉他合法加括号的方法总数。由于你在编程方面有比较大优势，其他同学都推荐你来回答这个问题。为了不辜负同学们的期望，更为了维护信息组的良好声誉，你可一定要回答好这个问题呀！！！

输入

一个整数K（2<=K<=30）

输出

一个整数（方法数）TOTAL。

样例输入

4

样例输出

5

数据范围限制

对于40%的数据，K<=10;

对于70%的数据，K<=20;

对于100%的数据， K<=30。

---

设f[i]为k个因数的Max

状态转移方程：f[i]=f[i]+f[j]*f[i-j]

---

代码如下：

#include
     
      #include
      
       using namespace std;int main(){    freopen("bracket.in","r",stdin);    freopen("bracket.out","w",stdout);    unsigned long long f[30]={
    0};    int n;    scanf("%d",&n);    f[1]=1;    for (int i=2;i<=n;i++) for (int j=1;j<=i-1;j++) f[i]=f[i]+f[j]*f[i-j];    printf("%lld",f[n]);    return 0;}