uva 10312——Expression Bracketing

野性酷女 2022-08-09 13:47 39阅读 0赞

In this problem you will have to find in how many ways **n** letters can be bracketed so that the bracketing is non-binary bracketing. For example **4** letters have **11** possible bracketing:

**xxxx, (xx)xx, x(xx)x, xx(xx), (xxx)x, x(xxx), ((xx)x)x, (x(xx))x, (xx)(xx), x((xx)x), x(x(xx))**. Of these the first six bracketing are not binary. Given the number of letters you will have to find the total number of non-binary bracketing.

**Input**

The input file contains several lines of input. Each line contains a single integer **n (0**. Input is terminated by end of file.

**Output**

For each line of input produce one line of output which denotes the number of non binary bracketing with **n** letters.

**Sample Input**

3  
4  
5  
10

**Sample Output**

1  
6  
31  
98187

题意：给你n个相乘的x，可以用括号来改变优先级，问在所有的情况中，有多少个是非二叉树的情况（开始没理解，后来查了binary的所有意思，二进制，二叉树，二分，看到二叉树，想到不久前水图论的时候看到的二叉树表达式，通了）。

思路：挣扎了两三天，并不知道从哪里下手，后来观察题目要求的反面，突然觉得有点眼熟，画了二叉树，恍然大悟就是卡特兰数啊，具体的卡特兰数的分析：[卡特兰数的性质及其应用][Link 1]

里面已经讲了卡特兰和超卡特兰，本题就是用超卡特兰减去卡塔兰。

Code：

//方法一：
    #include <iostream>
    #include <cstdlib>
    
    using namespace std;
    
    long long C[30] = {0};
    long long S[30] = {0};
    
    int main()
    {
        
    	S[0] = S[1] = S[2] = 1;
    	for (int i = 3 ; i < 30 ; ++ i)
    		S[i] = (3*(2*i-3)*S[i-1]-(i-3)*S[i-2])/i;
    	C[0] = C[1] = 1;
    	for (int i = 2 ; i < 30 ; ++ i)
    		for (int j = 0 ; j < i ; ++ j)
    			C[i] += C[j]*C[i-j-1];
    
    	int n;
    	while (cin >> n)
    		cout << S[n]-C[n-1] << endl;
    
    	return 0;
    }
    
    
    //方法二直接交表
    #include <iostream>
    #include <string>
    #include <cstring>
    #include <cstdio>
    using namespace std;
    
    typedef long long ll;
    const int N=27;
    ll super_catalan[N]={0,1,1,3,11,45,197,903,4279,20793,103049,518859,2646723,13648869,71039373,372693519,1968801519,10463578353,55909013009,300159426963,1618362158587,8759309660445,47574827600981,259215937709463,1416461675464871,7760733824437545,42624971294485657};
    ll catalan[N]={0,1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452};
    int main()
    {
        
        int n;
        while (~scanf("%d",&n)&&n)
            printf("%lld\n",super_catalan[n]-catalan[n]);
    }

[Link 1]: http://dedream.blog.163.com/blog/static/2434830452015631104250598/