10157 - Expressions
Time limit: 10.000 seconds
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=34&page=show_problem&problem=1098
Let X be the set of correctly built parenthesis expressions. The elements of X are strings consisting only of the characters "("and ")". The set X is defined as follows:
an empty string belongs to X
if A belongs to X, then (A) belongs to X
if both A and B belong to X, then the concatenation AB belongs to X.
For example, the following strings are correctly built parenthesis expressions (and therefore belong to the set X):
()(())()
(()(()))
The expressions below are not correctly built parenthesis expressions (and are thus not in X):
(()))(()
())(()
Let E be a correctly built parenthesis expression (therefore E is a string belonging to X).
The length of E is the number of single parenthesis (characters) in E.
The depth D(E) of E is defined as follows:
ì 0 if E is empty
D(E)= í D(A)+1 if E = (A), and A is in X
max(D(A),D(B)) if E = AB, and A, B are in X
For example, the length of "()(())()" is 8, and its depth is 2.
What is the number of correctly built parenthesis expressions of length n and depth d, for given positive integers n and d?
Task
Write a program which
reads two integers n and d
computes the number of correctly built parenthesis expressions of length n and depth d;
Input data
Input consists of lines of pairs of two integers - n and d, at most one pair on line, 2<= n<= 300, 1<= d<= 150.
The number of lines in the input file is at most 20, the input may contain empty lines, which you don't need to consider.
Output data
For every pair of integers in the input write single integer on one line - the number of correctly built parenthesis expressions of length n and depth d.
Example
Input data Output data
6 2 3
300 150 1
There are exactly three correctly built parenthesis expressions of length 6 and depth 2:
(())()
()(())
(()())
思路：
本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45358.htm
我们可以把最左边的“(”和其配对的“)”看成一组分界线，它们把剩余的括号分成了左右两部分，其中左边的深度最多为d-1，右边部分的深度最多为d。
接下来枚举左右两边的括号数，把每种情况累加即可。
使用递归，设f[n][d]表示一共有n对括号时深度不超过d的表达式的数量，那么f(n,d) = sum{f(i, d - 1)*f(n - i - 1, d)} (0<=i<n)，最后输出的结果即是f(n/2,d)-f(n/2,d-1)。
注意：题目保证了输入的括号串是合法的（n保证是偶数）。
完整代码：
/*0.752s*/
import java.io.*;
import java.util.*;
import java.math.*;
public class Main {
static Scanner cin = new Scanner(new BufferedInputStream(System.in));
static BigInteger[][] f = new BigInteger[151][151];
static boolean[][] vis = new boolean[151][151];
static BigInteger DP(int n, int d) {
if (vis[n][d])
return f[n][d];
vis[n][d] = true;
if (n <= 1 || d <= 1)
return f[n][d] = BigInteger.ONE;
f[n][d] = BigInteger.ZERO;
for (int i = 0; i < n; i++)
f[n][d] = f[n][d].add(DP(i, d - 1).multiply(DP(n - i - 1, d)));
return f[n][d];
}
public static void main(String[] args) {
for (int i = 0; i < 151; i++) {
f[i][0] = f[i][1] = f[0][i] = f[1][i] = BigInteger.ONE;
for (int j = 0; j < 151; j++)
vis[i][j] = false;
}
while (cin.hasNext()) {
int n = cin.nextInt(), d = cin.nextInt();
if (n <= 2 || d <= 1) {
System.out.println("1");
continue;
}
n >>= 1;
DP(n, d);
DP(n, d - 1);
System.out.println(f[n][d].subtract(f[n][d - 1]));
}
}
}
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索length
， and
， of
The
乐高10157、10157、，以便于您获取更多的相关知识。