题目大意:给出一个序列,长度为n,表示有n个x(节点),可以添加任意括号,问说形成的串为非二叉表达式的有多少个。
解题思路:直接求非二叉表达式是比较困难,所以换求总数减去二叉表达式的数量。二叉表达式的很容易发现是Catalan数,而总数时一种叫SuperCatalan数的一种序列,第一次接触。或者可以用dp做,i个节点,dp[i][0]表示该位置至少被差分成两个子树,dp[i][1]表示可以为1棵子树。
解法一:
#include <cstdio>
#include <cstring>
const int N = 30;
typedef long long ll;
ll f[N], b[N];
void init () {
int n = 26;
b[1] = b[2] = 1;
for (int i = 3; i <= n; i++)
b[i] = b[i-1] * (4*i-6) / i;
f[1] = f[2] = 1;
for (int i = 3; i <= n; i++)
f[i] = (3 * (2 * i - 3) * f[i-1] - (i - 3) * f[i-2])/i;
}
int main () {
init();
int n;
while (scanf("%d", &n) == 1) {
printf("%lld\n", f[n] - b[n]);
}
return 0;
}
解法二:
#include <cstdio>
#include <cstring>
typedef long long ll;
const int N = 30;
ll f[N], dp[N][2];
ll solve (int n, int s) {
ll& ans = dp[n][s];
if (~ans)
return ans;
if (n <= 1)
return ans = 1;
ans = 0;
for (int i = 1; i < n + s; i++)
ans += solve(i, 1) * solve(n-i, 0);
return ans;
}
int main () {
f[1] = f[2] = 1;
for (int i = 3; i <= 26; i++)
f[i] = f[i-1] * (4*i-6) / i;
int n;
while (scanf("%d", &n) == 1) {
memset(dp, -1, sizeof(dp));
printf("%lld\n", solve(n, 0) - f[n]);
}
return 0;
}
分享到:
相关推荐
C----------------------------------------------------------------------- program runocc C----------------------------------------------------------------------- c C OCCAM 2.0: Steven Constable IGPP/...
OSL dating of loess deposits bracketing Sheep Creek tephra beds
For Example: $ python>>> from pynumethods.bracketing import bisection>>> bisection( ' x^2-8x+11 ' , 1, 2, 0.001)1.7646484375计划功能: 库的GUI包装器贡献目前,我没有解决任何问题或进行更新的计划,因为...
Research on Statistical Machine Translation Based on Bracketing Transduction Grammar and Dependency Grammar_xiongdeyi_phd thesis 2007.pdf Research on Implementation Technology of Large-scale ...
TeamBracket
Chapter 5 Roots: Bracketing Methods Chapter 6 Roots: Open Methods Chapter 7 Optimization Part Three: Linear Systems Chapter 8 Linear Algebraic Equations and Matrices Chapter 9 Gauss Elimination ...
二分法是求解超越方程的所有数值方案中最简单的。... 这如需任何参考,请访问: https : //mat.iitm.ac.in/home/sryedida/public_html/caimna/transcendental/bracketing methods/bisection/bisection.html#problems
Network Security: Private Communication in a Public World, Second Edition By Charlie Kaufman, Radia Perlman, Mike Speciner ............................................... Publisher: Prentice Hall ...
$ git clone https://github.com/bracketing/bracket $ cd bracket $ python setup.py install 一个简单的例子 from bracket import WebSite from jinja2 import Template app = WebSite ( __name__ ) @ app . ...
" bracketing around the macros * allows the err_abort and errno_abort macros to be used as if they * were function calls, even in contexts where a trailing ";" would * generate a null statement. ...