首页 > 代码库 > UVA10312- Expression Bracketing(Catalan + 递推)

UVA10312- Expression Bracketing(Catalan + 递推)

题目链接


题意:给出一个序列,长度为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;
}


UVA10312- Expression Bracketing(Catalan + 递推)