logo AlgoBeat OnlineJudge
登录 注册

#214953. [海淀区普及组 2025 T2] 括号构造大赛

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

元旦联欢会上,老师为信息学社团的同学举办了构造大赛,由老师给出两个括号序列,看谁能最快构造出最短的满足要求的括号序列,具体规则如下:对于两个字符串 ,若字符串 的一个子序列(不要求连续),则称 包含了

给出两个只由 () 组成的括号串 。你需要构造一个字符串 ,要求同时满足:

  1. 字符串 包含
  2. 字符串 包含
  3. 是一个合法括号串。

构造大赛要求学生写出一种 的具体方案,但为了方便,你只需要求出满足上述条件的字符串 的最短长度即可。

其中,合法括号串定义如下:

  1. () 是合法括号串;
  2. 是合法括号串,则 也是合法括号串;
  3. 都是合法括号串,则 也是合法括号串。

输入格式

第一行输入一个字符串 )。 第二行输入一个字符串 )。

输出格式

一个正整数,表示最短的包含 的括号序列长度。

样例

样例输入 1

(())(()
()))()

样例输出 1

8

样例输入 2

)
((

样例输出 2

4

样例输入 3

)
)))

样例输出 3

6

样例输入 4

())
(()(()(()(

样例输出 4

14

数据范围与提示

样例 1 解释:

合法的序列可以是 (())()()

数据范围:

对于前 30% 的数据,满足输入的括号串长度分别不超过10。

对于另外 30% 数据,满足输入的 串长度等于 1。

对于所有数据,满足“输入格式”中给出的数据范围。