option=com_onlinejudge&Itemid=8&page=show_problem&problem=1253">题目链接

题意：给出一个序列，长度为n，表示有n个x(节点)，能够加入随意括号。问说形成的串为非二叉表达式的有多少个。

思路：用总数减去二叉表达式的数量。二叉表达式能够用Catalan数求解，至于总数的话，用dp求解。dp[i][0]表示在第i个位置能够被拆分成两个子树，dp[i][1]表示有一个子树。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 30;

ll Catalan[MAXN], dp[MAXN][2];

int n;

void init() {

    memset(Catalan, 0, sizeof(Catalan));

    Catalan[1] = Catalan[2] = 1;

    for (int i = 3; i < MAXN; i++)

        Catalan[i] = Catalan[i - 1] * (4 * i - 6) / i;

}

ll dfs(int n, int m) {

    ll& ans = dp[n][m];

    if (ans != 0)

        return ans;

    if (n <= 1)

        return 1;

    ans = 0;

    for (int i = 1; i < n + m; i++)

        ans += dfs(i, 1) * dfs(n - i, 0);

    return ans;

}

int main() {

    init();

    while (scanf("%d", &n) != EOF) {

        memset(dp, 0, sizeof(dp));

        printf("%lld\n", dfs(n, 0) - Catalan[n]);

    }

    return 0;

}