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 ofcorrectly 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).
Thelengthof E is the number of single parenthesis (characters) in E.
ThedepthD(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 lengthnand depthd, 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 dataInput 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:
(())()
()(())
(()())
思路:
我们可以把最左边的“(”和其配对的“)”看成一组分界线,它们把剩余的括号分成了左右两部分,其中左边的深度最多为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]));
}
}
}
分享到:
相关推荐
Mastering Regular Expressions 3rd
regular expressions.
Introducing Regular Expressions pdf 高清 有目錄
Z.Expressions.Eval 4.0.68 包含.net3.1和 .net6的支持。不需要key,去除限制。
Walk away from old-fashioned and cumbersome query approaches and answer your business intelligence questions through simple and powerful queries built on common table expressions (CTEs) and window ...
书名:Mastering Regular Expressions, 3rd Edition 格式:CHM 语言:English 简介: Regular expressions are an extremely powerful tool for manipulating text and data. They are now standard ...
带有正则表达式的应用程序。 简约的UI 忘记按钮。只需键入您的模式并测试表达式。立即查看结果。 突出显示语法 不仅看起来不错,而且易于阅读。 参考表 总是忘记正则表达式的语法吗?只需按cmd r并查看参考表...
如果您曾经不得不对数学表达式进行排版,您可能会想过:如果我可以给手写表达式拍照并自动识别它,那不是很好吗?该数据集包含构建系统所需的所有数据。该数据集融合了来自4个CROHME竞赛的数据集,提供了来自不同...
JavaScript Regular Expressions 英文无水印pdf pdf所有页面使用FoxitReader和PDF-XChangeViewer测试都可以打开 本资源转载自网络,如有侵权,请联系上传者或csdn删除 本资源转载自网络,如有侵权,请联系上传...
公式操作、表达式动态语句,可以考虑使用 Eval Expression。 本文件给你无限使用的特权,基于netstand2.1制作,可以方便的...需要下列包 ... <PackageReference Include="System.Xml.XPath" Version="4.3.0" />
Mastering Regular Expressions, 2nd Edition
You will begin by discovering what regular expressions are and how they work with Java. This easy-to-follow guide is a great place from which to familiarize yourself with the core concepts of regular ...
MariaDB and MySQL Common Table Expressions and Window Functions Revealed 英文epub 本资源转载自网络,如有侵权,请联系上传者或csdn删除 本资源转载自网络,如有侵权,请联系上传者或csdn删除
Mastering Regular Expressions.pdf
Teradata SQL Functions, Operators, Expressions, and Predicates
Regular expressions are used to describe patterns in text, and they are an invaluable aid when working with loosely formatted textual data. This little booklet describes Oracle's regular expression ...
Mastering Regular Expressions(3rd) 英文无水印pdf 第3版 pdf所有页面使用FoxitReader和PDF-XChangeViewer测试都可以打开 本资源转载自网络,如有侵权,请联系上传者或csdn删除 本资源转载自网络,如有侵权,...
[Regular.Expressions.Cookbook(2nd,2012,8)].Jan.Goyvaerts
用于正则表达式测试的简单工具,简单方便快捷。能快速测出正则表达式的功能