题目详情题解（0）讨论（0）提交记录（0）

AT_agc054_d.[AGC054D] (ox)

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个由 (、)、o、x 组成的字符串 SS。你可以任意次数地交换 SS 中相邻的两个字符。请你求出，为了满足下述条件，所需的最小操作次数。

  • 将 SS 中出现的每个 o 替换为 ()，每个 x 替换为 )(，从而得到仅由 ( 和 ) 组成的新字符串 S′S'。此时，S′S' 必须是括号匹配的字符串。

括号匹配的字符串定义如下：

  • 空字符串；
  • 存在括号匹配的非空字符串 ss、tt，将 ss 和 tt 按此顺序连接得到的字符串；
  • 存在括号匹配的字符串 ss，将 (、ss、) 按此顺序连接得到的字符串。

此外，根据本题的限制条件，目标一定可以实现。

输入格式

输入为一行，包含一个字符串 SS。

输出格式

输出所需的最小操作次数。

输入输出样例

  • 输入#1

    )x(

    输出#1

    3

  • 输入#2

    ()ox

    输出#2

    2

  • 输入#3

    ()oxo(xxx))))oox((oooxxoxo)oxo)ooo(xxx(oox(x)(x()x

    输出#3

    68

说明/提示

限制

  • SS 仅由 (、)、o、x 组成。
  • SS 至少包含一个 ( 和一个 )，且它们的数量相等。
  • ∣S∣≤8000|S| \leq 8000

样例解释 1

)x( → x)( → x() → (x)，这样操作即可。此时 $S' = ()()`，它是一个括号匹配的字符串。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页