UVA10312- Expression Bracketing(Catalan + 递推)
expression 递推
2023-09-14 09:06:25 时间
题意:给出一个序列,长度为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; }
相关文章
- [Regex Expression] Tagline --- {0, } {1,10}
- [Regex Expression] Match mutli-line number, number range
- [Regex Expression] Confirmative -- World bundry
- [Regex Expression] Find Sets of Characters
- CSS中的行为——expression
- Chrome 开发者工具 live expression 的用法
- use regular expression instead of ABAP function module to parse attachment
- Attachment multiple read API - performance with regular expression
- Sql Server substring(expression, start, length)函数
- Type of expression is ambiguous without more context
- jQuery操作表格背景色迭代和鼠标移动事件(CSS中使用expression)
- SyntaxError: expected expression, got ")" void() : 1: 5
- 从all-merged-Graph-Based Genes.csv 提取出 average expression avglogfc 或者pval doheatmap
- PAT 1130 Infix Expression[难][dfs]
- dp好题 玲珑杯 Expected value of the expression
- MySQL ---- In aggregated query without GROUP BY, expression #2 of SELECT list contains nonaggregated