首页 > 代码库 > 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 + 递推)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。