Problem G: 括号序列
| Time Limit |
$1$ 秒/Second(s) |
Memory Limit |
$512$ 兆字节/Megabyte(s) |
| 提交总数 |
$353$ |
正确数量 |
$79$ |
"
| 裁判形式 |
标准裁判/Standard Judge |
我的状态 |
尚未尝试 |
| 难度 |
|
分类标签 |
递归 动态规划 |
当前分类(单击移除)：
递归动态规划
单击选择分类：
括号序列是指由“和)组成的序列，假如一个括号序列中，包含相同数量的左括
号和右括号，并且对于每一个右括号，在他的左侧都有左括号和他匹配，则这个
括号序列就是一个合法括号序列。比如(())()就是一个合法括号序列，但
(()) ( ()不是合法括号序列。
给出两个长度相同的合法括号序列A和B,那么A<B当且仅当:
●A和B 至少有一位不相同。
●在A和B从左往右数第一个不相同的位置i, A[i]=(, B[i]=)
比如A=(())()，B=()()()，则A<B,因为从左边数第一个不相同的
是第二个字符，A[2] = (,B[2] = ).对于长度N,由于定义了小于关系，
则可以通过这个关系推出所有长度为N的合法括号序列的大小关系，对于长度
为6的合法括号序列，从小到大排列顺序如下:
1. ((()))
2.(()())
3. (()) ()
4.()(())
5.()()()
给出N和M,求长度为N的合法括号序列中，
第M小的合法括号序列是?