Brackets
Time Limit: 1000MS |
|
Memory Limit: 65536K |
Total Submissions: 1659 |
|
Accepted: 831 |
Description
We give the following inductive definition of a “regular brackets” sequence:
- the empty sequence is a regular brackets sequence,
- if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and
- if a and b are regular brackets sequences, then ab is a regular brackets sequence.
- no other sequence is a regular brackets sequence
For instance, all of the following character sequences are regular brackets sequences:
(), [], (()), ()[], ()[()]
while the following character sequences are not:
(, ], )(, ([)], ([(]
Given a brackets sequence of characters a1a2 …
an, your goal is to find the length of the longest regular brackets sequence that is a subsequence of
s. That is, you wish to find the largest m such that for indices
i1, i2, …, im where 1 ≤
i1 < i2 < … < im ≤
n, ai1ai2 …
aim is a regular brackets sequence.
Given the initial sequence ([([]])]
, the longest regular brackets subsequence is
[([])]
.
Input
The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters
(
, )
, [
, and ]
; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed.
Output
For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line.
Sample Input
((()))
()()()
([]])
)[)(
([][][)
end
Sample Output
6
6
4
0
6
Source
分享到:
相关推荐
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
PKU Online Judge上面很全面的动态规划试题总结。动态规划是ACM考点中最重要的一大类算法之一,对于工作人员来说,动态规划也是实际开发中...这是POJ上面很多DP题目的总结与深刻分析。利于算法学习,学长给的,在此分享
北大POJ1015-Jury Compromise【动态规划DP】 解题报告+AC代码
动态规划DP题解 POJ HDU部分动态规划DP题解
OJ动态规划DP题目列表 POJ SOJ HDU 动态规划题目
这是黑不来就的poj上的所有dp题目的大型分类 好使好用
动态规划DP题解 POJ HDU 动态规划解题报告
POJ上的DP分类: 容易: 1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740(博弈), 1742, 1887, 1926(马尔科夫矩阵,求...
POJ 动态规划总结 背包之01背包、完全背包、多重背包详解 Dynamic+Programming 典型的动态规划,用递归下的记忆化搜索来实现 1088 POJ 动态规划加速原理之四边形不等式 基于连通性状态压缩的动态规划问题 对一些DP...
这是一道很不错的题目,dp解决的经典例子,是学习dp,和练习的好题目。。。。
Poj 3342 这是一道树状dp题目,题意是这样的,一个公司,每个人有且仅有一个Boss,除了最大的Boss没有Boss(显然),现在要参加一个聚会,要求参加的人数最多,但是棘手的.......
2遍dp poj_3613解题报告 poj_3613解题报告
poj2342,树形dp,dp[i][0]表示i不参加party,其下属(包括非直接下属)能得到的最优值。dp[i][1]表示i参加的其下属和他能得到的最优值。
北大POJ3411-Paid Roads【class】 解题报告+AC代码
3.线性的动态规划问题 积木游戏问题 决斗(判定性问题) 圆的最大多边形问题 统计单词个数问题 棋盘分割 日程安排问题 最小逼近问题(求出两数之比最接近某数/两数之和等于某数等等) 方块消除游戏(某区间可以...
坐标型动态规划 poj1191棋盘分割 poj1088滑雪 noi过河卒 动态规划的解题思想及思路
2.DP(动态规划) 3.贪心 4.图论 //Dijkstra、最小生成树、网络流 5.数论 //解模线性方程 6.计算几何 //凸壳、同等安置矩形的并的面积与周长 7.组合数学 //Polya定理 8.模拟 9.数据结构 //并查集、堆 10....
讲解 poj 2564做法。 解题思路是DP+字典树,挺好的一题,文件里面包括思路和代码。
本人的一些poj基础训练题,主要包括图论,大数,二叉搜索,DP,搜索,hash等内容的入门题的ac源代码,代码风格容易模仿,适合acm入门级爱好者,题目涵盖范围对于入门者大约需要3至6个月左右的学习时间(有acm参加...
acm poj 比较详细的将poj的题目进行了分类,如dp,搜索,数据结构等等