题目背景
八云紫拥有操控境界程度的能力。作为其式神的八云蓝,同样拥有一定程度的操作境界的能力,而作为八云蓝的式神橙,却因为功力尚且不足,而无法对境界进行过多的干预了。
于是八云蓝打算教教橙,境界的用法。境界可以被抽象成一层一层的括号,操作境界本质上就是对括号序列进行修改。由于橙的能力尚且不足,因此只能进行一些简单的境界的建立与摧毁。
尽管如此,通过简单的操作,亦可以把一个境界转换为另外一个境界。为了给橙作为练习,蓝找来了两个境界的范本。将其中一个境界转换为另外一个境界的难度,就是橙需要施用能力的最小次数。但是由于境界实在太长,蓝决定写一个程序(?)来帮帮她计算出境界的难度。
题目描述
境界可以被抽象为由圆括号组成的括号序列。现做出如下定义:
- 定义 Di 为嵌套括号序列。其中 D0 为零阶嵌套括号序列,被定义为单组括号 ();而 Dk 则为 k 阶嵌套括号序列(k≥1)定义为 (Dk−1),即在 Dk−1 的外层增添了一层括号。
- 定义 Fi 为平铺括号序列。其中 F0 为零阶平铺括号序列,被定义为单组括号 ();而 Fk 则为 k 阶平铺括号序列(k≥1),定义为 ()Fk−1,即在 Fk−1 的左侧增添了一对括号。
例如,((())) 为 D2,()()()() 为 F3。
现在蓝给出了两个长度为 n 的合法括号序列 A 和 B。橙可以用以下操作对序列 A 进行变换:
- 选择任意非负整数 k,选择括号序列的一个子串满足其为一个 k 阶嵌套括号序列,然后将其变为 k 阶平铺括号序列。
- 选择任意非负整数 k,选择括号序列的一个子串满足其为一个 k 阶平铺括号序列,然后将其变为 k 阶嵌套括号序列。
提示说明处有「合法括号序列」与「子串」的定义。
现在需要求出将序列 A 变换为序列 B 所需的最少操作数。可以证明,总存在一种操作方案能将序列 A 变换为序列 B。
输入格式
- 第一行共有一个整数 n,表示 A 与 B 括号序列的长度。
- 接下来一行,共有 n 个字符,描述括号序列 A。保证序列 A 合法。
- 接下来一行,共有 n 个字符,描述括号序列 B。保证序列 B 合法。
输出格式
- 共一行,一个整数,表示将 A 转换为 B 需要的最少步数(可能为 0,也就是不进行任何操作)。
提示
样例 3 见下发的附件 border3.in/border3.ans。
样例 4 见下发的附件 border4.in/border4.ans。满足特殊性质 A(见下文)。
样例 5 见下发的附件 border5.in/border5.ans。
样例 1 解释
- 第一步:((()())(()()))→(((()))(()()))。
- 第二步:(((()))(()()))→(((()))((())))。
- 第三步:(((()))((())))→(((()))()()())。
- 第四步:(((()))()()())→(()()()()()())。
- 第五步:(()()()()()())→((((((()))))))。
- 第六步:((((((()))))))→()()()()()()()。
可以证明,不存在更短的方案。
提示
合法括号序列通过这样一个形式定义:
- () 是合法括号序列。
- 若 A 是合法括号序列,那么 (A) 是合法括号序列。
- 若 A,B 均为合法括号序列,那么 AB 是合法括号序列。
我们称 A 是 B 的子串,当且仅当删除 B 开头若干个字符(可以不删除),再删除 B 末尾若干个字符(可以不删除),剩下来的字符序列与 A 完全相同。
数据范围及约定
本题共有 20 个测试点,每个测试点 5 分。最终分数为所有测试点分数之和。
Task1∼45∼78∼1011∼1516∼20n≤102×1032×103106106特殊性质−A−A−特殊性质 A:保证 B 是 (n÷2−1) 阶平铺括号序列。
友情提醒
考虑到选手可能会用不同的方式进行字符串的读入,这里保证输入文件每行末尾没有多余空格,并且每行都以 \n
结尾(也就是说,不会出现多余的 \r
)。