分数: 1000 点
问题陈述
给定的是一个字符串 S 组成 (, ), o,和 x。
您可以交换两个相邻的字符 S 任意次数。
求满足以下条件所需的最小交换次数。
- 让我们制作一个字符串 S' 组成
(和)通过替换每个出现的o与()以及每次出现x与)(in S。 然后, S' 是 平衡括号字符串.
平衡括号字符串的定义
平衡括号字符串是以下字符串之一:
- 空字符串;
- 一个串联的字符串 s, t 按此顺序,其中 s 和 t 是一些非空平衡括号字符串;
- 一个串联的字符串
(, s,)按此顺序,其中 s 是一些平衡的括号字符串。
在这个问题的约束下,总是可以达到目的的。
约束
- S 是一个由以下组成的字符串
(,),o,和x. - S 包含相同的非零数量
(和)s。 - |S| \leq 8000
输入
输入由标准输入按以下格式给出:
S
输出
打印答案。
示例输入 1
)x(
示例输出 1
3
我们应该这样做: )x( → x)( → x() → (x)。
在这里,我们有 S'=()(),这是一个平衡的括号字符串。
示例输入 2
()ox
示例输出 2
2
示例输入 3
()oxo(xxx))))oox((oooxxoxo)oxo)ooo(xxx(oox(x)(x()x
示例输出 3
68